<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><link rel="stylesheet" type="text/css" href="style.css" /><script type="text/javascript" src="highlight.js"></script></head><body><pre><span class="hs-pragma">{-# LANGUAGE BangPatterns         #-}</span><span>
</span><span id="line-2"></span><span class="hs-pragma">{-# LANGUAGE CPP                  #-}</span><span>
</span><span id="line-3"></span><span class="hs-pragma">{-# LANGUAGE DeriveDataTypeable   #-}</span><span>
</span><span id="line-4"></span><span class="hs-pragma">{-# LANGUAGE FlexibleContexts     #-}</span><span>
</span><span id="line-5"></span><span class="hs-pragma">{-# LANGUAGE ScopedTypeVariables  #-}</span><span>
</span><span id="line-6"></span><span class="hs-pragma">{-# LANGUAGE TypeFamilies         #-}</span><span>
</span><span id="line-7"></span><span class="hs-pragma">{-# LANGUAGE UndecidableInstances #-}</span><span>
</span><span id="line-8"></span><span class="hs-comment">-----------------------------------------------------------------------------</span><span>
</span><span id="line-9"></span><span class="hs-comment">-- |</span><span>
</span><span id="line-10"></span><span class="hs-comment">-- Module      :  Distribution.Compat.Graph</span><span>
</span><span id="line-11"></span><span class="hs-comment">-- Copyright   :  (c) Edward Z. Yang 2016</span><span>
</span><span id="line-12"></span><span class="hs-comment">-- License     :  BSD3</span><span>
</span><span id="line-13"></span><span class="hs-comment">--</span><span>
</span><span id="line-14"></span><span class="hs-comment">-- Maintainer  :  cabal-dev@haskell.org</span><span>
</span><span id="line-15"></span><span class="hs-comment">-- Stability   :  experimental</span><span>
</span><span id="line-16"></span><span class="hs-comment">-- Portability :  portable</span><span>
</span><span id="line-17"></span><span class="hs-comment">--</span><span>
</span><span id="line-18"></span><span class="hs-comment">-- A data type representing directed graphs, backed by &quot;Data.Graph&quot;.</span><span>
</span><span id="line-19"></span><span class="hs-comment">-- It is strict in the node type.</span><span>
</span><span id="line-20"></span><span class="hs-comment">--</span><span>
</span><span id="line-21"></span><span class="hs-comment">-- This is an alternative interface to &quot;Data.Graph&quot;.  In this interface,</span><span>
</span><span id="line-22"></span><span class="hs-comment">-- nodes (identified by the 'IsNode' type class) are associated with a</span><span>
</span><span id="line-23"></span><span class="hs-comment">-- key and record the keys of their neighbors.  This interface is more</span><span>
</span><span id="line-24"></span><span class="hs-comment">-- convenient than 'Data.Graph.Graph', which requires vertices to be</span><span>
</span><span id="line-25"></span><span class="hs-comment">-- explicitly handled by integer indexes.</span><span>
</span><span id="line-26"></span><span class="hs-comment">--</span><span>
</span><span id="line-27"></span><span class="hs-comment">-- The current implementation has somewhat peculiar performance</span><span>
</span><span id="line-28"></span><span class="hs-comment">-- characteristics.  The asymptotics of all map-like operations mirror</span><span>
</span><span id="line-29"></span><span class="hs-comment">-- their counterparts in &quot;Data.Map&quot;.  However, to perform a graph</span><span>
</span><span id="line-30"></span><span class="hs-comment">-- operation, we first must build the &quot;Data.Graph&quot; representation, an</span><span>
</span><span id="line-31"></span><span class="hs-comment">-- operation that takes /O(V + E log V)/.  However, this operation can</span><span>
</span><span id="line-32"></span><span class="hs-comment">-- be amortized across all queries on that particular graph.</span><span>
</span><span id="line-33"></span><span class="hs-comment">--</span><span>
</span><span id="line-34"></span><span class="hs-comment">-- Some nodes may be broken, i.e., refer to neighbors which are not</span><span>
</span><span id="line-35"></span><span class="hs-comment">-- stored in the graph.  In our graph algorithms, we transparently</span><span>
</span><span id="line-36"></span><span class="hs-comment">-- ignore such edges; however, you can easily query for the broken</span><span>
</span><span id="line-37"></span><span class="hs-comment">-- vertices of a graph using 'broken' (and should, e.g., to ensure that</span><span>
</span><span id="line-38"></span><span class="hs-comment">-- a closure of a graph is well-formed.)  It's possible to take a closed</span><span>
</span><span id="line-39"></span><span class="hs-comment">-- subset of a broken graph and get a well-formed graph.</span><span>
</span><span id="line-40"></span><span class="hs-comment">--</span><span>
</span><span id="line-41"></span><span class="hs-comment">-----------------------------------------------------------------------------</span><span>
</span><span id="line-42"></span><span>
</span><span id="line-43"></span><span class="hs-keyword">module</span><span> </span><span class="hs-identifier">Distribution.Compat.Graph</span><span> </span><span class="hs-special">(</span><span>
</span><span id="line-44"></span><span>    </span><span class="annot"><span class="hs-comment">-- * Graph type</span></span><span>
</span><span id="line-45"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier">Graph</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-46"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#IsNode"><span class="hs-identifier">IsNode</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">,</span><span>
</span><span id="line-47"></span><span>    </span><span class="annot"><span class="hs-comment">-- * Query</span></span><span>
</span><span id="line-48"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#null"><span class="hs-identifier">null</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-49"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#size"><span class="hs-identifier">size</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-50"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#member"><span class="hs-identifier">member</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-51"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#lookup"><span class="hs-identifier">lookup</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-52"></span><span>    </span><span class="annot"><span class="hs-comment">-- * Construction</span></span><span>
</span><span id="line-53"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#empty"><span class="hs-identifier">empty</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-54"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#insert"><span class="hs-identifier">insert</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-55"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#deleteKey"><span class="hs-identifier">deleteKey</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-56"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#deleteLookup"><span class="hs-identifier">deleteLookup</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-57"></span><span>    </span><span class="annot"><span class="hs-comment">-- * Combine</span></span><span>
</span><span id="line-58"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#unionLeft"><span class="hs-identifier">unionLeft</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-59"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#unionRight"><span class="hs-identifier">unionRight</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-60"></span><span>    </span><span class="annot"><span class="hs-comment">-- * Graph algorithms</span></span><span>
</span><span id="line-61"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#stronglyConnComp"><span class="hs-identifier">stronglyConnComp</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-62"></span><span>    </span><span class="annot"><a href="../../containers/src/Data.Graph.html#SCC"><span class="hs-identifier">SCC</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">,</span><span>
</span><span id="line-63"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#cycles"><span class="hs-identifier">cycles</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-64"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#broken"><span class="hs-identifier">broken</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-65"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#neighbors"><span class="hs-identifier">neighbors</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-66"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#revNeighbors"><span class="hs-identifier">revNeighbors</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-67"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#closure"><span class="hs-identifier">closure</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-68"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#revClosure"><span class="hs-identifier">revClosure</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-69"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#topSort"><span class="hs-identifier">topSort</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-70"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#revTopSort"><span class="hs-identifier">revTopSort</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-71"></span><span>    </span><span class="annot"><span class="hs-comment">-- * Conversions</span></span><span>
</span><span id="line-72"></span><span>    </span><span class="annot"><span class="hs-comment">-- ** Maps</span></span><span>
</span><span id="line-73"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#toMap"><span class="hs-identifier">toMap</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-74"></span><span>    </span><span class="annot"><span class="hs-comment">-- ** Lists</span></span><span>
</span><span id="line-75"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#fromDistinctList"><span class="hs-identifier">fromDistinctList</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-76"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#toList"><span class="hs-identifier">toList</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-77"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#keys"><span class="hs-identifier">keys</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-78"></span><span>    </span><span class="annot"><span class="hs-comment">-- ** Sets</span></span><span>
</span><span id="line-79"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#keysSet"><span class="hs-identifier">keysSet</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-80"></span><span>    </span><span class="annot"><span class="hs-comment">-- ** Graphs</span></span><span>
</span><span id="line-81"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#toGraph"><span class="hs-identifier">toGraph</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-82"></span><span>    </span><span class="annot"><span class="hs-comment">-- * Node type</span></span><span>
</span><span id="line-83"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#Node"><span class="hs-identifier">Node</span></a></span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">,</span><span>
</span><span id="line-84"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#nodeValue"><span class="hs-identifier">nodeValue</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-85"></span><span class="hs-special">)</span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-86"></span><span>
</span><span id="line-87"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="Distribution.Compat.Prelude.html"><span class="hs-identifier">Distribution.Compat.Prelude</span></a></span><span> </span><span class="hs-keyword">hiding</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../base/src/GHC.Base.html#empty"><span class="hs-identifier">empty</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../base/src/GHC.List.html#lookup"><span class="hs-identifier">lookup</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../base/src/Data.Foldable.html#null"><span class="hs-identifier">null</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../base/src/Data.Foldable.html#toList"><span class="hs-identifier">toList</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-88"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../base/src/Prelude.html#"><span class="hs-identifier">Prelude</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-special">)</span><span>
</span><span id="line-89"></span><span>
</span><span id="line-90"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../array/src/Data.Array.html#"><span class="hs-identifier">Data.Array</span></a></span><span>                    </span><span class="hs-special">(</span><span class="annot"><a href="../../base/src/GHC.Arr.html#%21"><span class="hs-operator">(!)</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-91"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="../../containers/src/Data.Graph.html#"><span class="hs-identifier">Data.Graph</span></a></span><span>                    </span><span class="hs-special">(</span><span class="annot"><a href="../../containers/src/Data.Graph.html#SCC"><span class="hs-identifier">SCC</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-92"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="Distribution.Utils.Structured.html"><span class="hs-identifier">Distribution.Utils.Structured</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Utils.Structured.html#Structure"><span class="hs-identifier">Structure</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Distribution.Utils.Structured.html#Structured"><span class="hs-identifier">Structured</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-93"></span><span>
</span><span id="line-94"></span><span class="hs-keyword">import</span><span> </span><span class="hs-keyword">qualified</span><span> </span><span class="annot"><a href="../../array/src/Data.Array.html#"><span class="hs-identifier">Data.Array</span></a></span><span>                  </span><span class="hs-keyword">as</span><span> </span><span class="annot"><span class="hs-identifier">Array</span></span><span>
</span><span id="line-95"></span><span class="hs-keyword">import</span><span> </span><span class="hs-keyword">qualified</span><span> </span><span class="annot"><a href="../../base/src/Data.Foldable.html#"><span class="hs-identifier">Data.Foldable</span></a></span><span>               </span><span class="hs-keyword">as</span><span> </span><span class="annot"><span class="hs-identifier">Foldable</span></span><span>
</span><span id="line-96"></span><span class="hs-keyword">import</span><span> </span><span class="hs-keyword">qualified</span><span> </span><span class="annot"><a href="../../containers/src/Data.Graph.html#"><span class="hs-identifier">Data.Graph</span></a></span><span>                  </span><span class="hs-keyword">as</span><span> </span><span class="annot"><span class="hs-identifier">G</span></span><span>
</span><span id="line-97"></span><span class="hs-keyword">import</span><span> </span><span class="hs-keyword">qualified</span><span> </span><span class="annot"><a href="../../containers/src/Data.Map.Strict.html#"><span class="hs-identifier">Data.Map.Strict</span></a></span><span>             </span><span class="hs-keyword">as</span><span> </span><span class="annot"><span class="hs-identifier">Map</span></span><span>
</span><span id="line-98"></span><span class="hs-keyword">import</span><span> </span><span class="hs-keyword">qualified</span><span> </span><span class="annot"><a href="../../containers/src/Data.Set.html#"><span class="hs-identifier">Data.Set</span></a></span><span>                    </span><span class="hs-keyword">as</span><span> </span><span class="annot"><span class="hs-identifier">Set</span></span><span>
</span><span id="line-99"></span><span class="hs-keyword">import</span><span> </span><span class="hs-keyword">qualified</span><span> </span><span class="annot"><a href="../../containers/src/Data.Tree.html#"><span class="hs-identifier">Data.Tree</span></a></span><span>                   </span><span class="hs-keyword">as</span><span> </span><span class="annot"><span class="hs-identifier">Tree</span></span><span>
</span><span id="line-100"></span><span class="hs-keyword">import</span><span> </span><span class="hs-keyword">qualified</span><span> </span><span class="annot"><a href="Distribution.Compat.Prelude.html"><span class="hs-identifier">Distribution.Compat.Prelude</span></a></span><span> </span><span class="hs-keyword">as</span><span> </span><span class="annot"><a href="../../base/src/Prelude.html#"><span class="hs-identifier">Prelude</span></a></span><span>
</span><span id="line-101"></span><span>
</span><span id="line-102"></span><span class="hs-comment">-- | A graph of nodes @a@.  The nodes are expected to have instance</span><span>
</span><span id="line-103"></span><span class="hs-comment">-- of class 'IsNode'.</span><span>
</span><span id="line-104"></span><span class="hs-keyword">data</span><span> </span><span id="Graph"><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-var">Graph</span></a></span></span><span> </span><span id="local-6989586621679651238"><span class="annot"><a href="#local-6989586621679651238"><span class="hs-identifier hs-type">a</span></a></span></span><span>
</span><span id="line-105"></span><span>    </span><span class="hs-glyph">=</span><span> </span><span id="Graph"><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-var">Graph</span></a></span></span><span> </span><span class="hs-special">{</span><span>
</span><span id="line-106"></span><span>        </span><span id="graphMap"><span class="annot"><span class="annottext">forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#graphMap"><span class="hs-identifier hs-var hs-var">graphMap</span></a></span></span><span>          </span><span class="hs-glyph">::</span><span> </span><span class="hs-glyph">!</span><span class="hs-special">(</span><span class="annot"><a href="../../containers/src/Data.Map.Internal.html#Map"><span class="hs-identifier hs-type">Map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651238"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><a href="#local-6989586621679651238"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span class="hs-special">,</span><span>
</span><span id="line-107"></span><span>        </span><span class="hs-comment">-- Lazily cached graph representation</span><span>
</span><span id="line-108"></span><span>        </span><span id="graphForward"><span class="annot"><span class="annottext">forall a. Graph a -&gt; Graph
</span><a href="Distribution.Compat.Graph.html#graphForward"><span class="hs-identifier hs-var hs-var">graphForward</span></a></span></span><span>      </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="../../containers/src/Data.Graph.html#Graph"><span class="hs-identifier hs-type">G.Graph</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-109"></span><span>        </span><span id="graphAdjoint"><span class="annot"><span class="annottext">forall a. Graph a -&gt; Graph
</span><a href="Distribution.Compat.Graph.html#graphAdjoint"><span class="hs-identifier hs-var hs-var">graphAdjoint</span></a></span></span><span>      </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="../../containers/src/Data.Graph.html#Graph"><span class="hs-identifier hs-type">G.Graph</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-110"></span><span>        </span><span id="graphVertexToNode"><span class="annot"><span class="annottext">forall a. Graph a -&gt; Vertex -&gt; a
</span><a href="Distribution.Compat.Graph.html#graphVertexToNode"><span class="hs-identifier hs-var hs-var">graphVertexToNode</span></a></span></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="../../containers/src/Data.Graph.html#Vertex"><span class="hs-identifier hs-type">G.Vertex</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679651238"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-111"></span><span>        </span><span id="graphKeyToVertex"><span class="annot"><span class="annottext">forall a. Graph a -&gt; Key a -&gt; Maybe Vertex
</span><a href="Distribution.Compat.Graph.html#graphKeyToVertex"><span class="hs-identifier hs-var hs-var">graphKeyToVertex</span></a></span></span><span>  </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651238"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Maybe"><span class="hs-identifier hs-type">Maybe</span></a></span><span> </span><span class="annot"><a href="../../containers/src/Data.Graph.html#Vertex"><span class="hs-identifier hs-type">G.Vertex</span></a></span><span class="hs-special">,</span><span>
</span><span id="line-112"></span><span>        </span><span id="graphBroken"><span class="annot"><span class="annottext">forall a. Graph a -&gt; [(a, [Key a])]
</span><a href="Distribution.Compat.Graph.html#graphBroken"><span class="hs-identifier hs-var hs-var">graphBroken</span></a></span></span><span>       </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">[</span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679651238"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">,</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651238"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span class="hs-special">)</span><span class="hs-special">]</span><span>
</span><span id="line-113"></span><span>    </span><span class="hs-special">}</span><span>
</span><span id="line-114"></span><span>    </span><span class="hs-keyword">deriving</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../base/src/Data.Typeable.Internal.html#Typeable"><span class="hs-identifier hs-type">Typeable</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-115"></span><span>
</span><span id="line-116"></span><span class="hs-comment">-- NB: Not a Functor! (or Traversable), because you need</span><span>
</span><span id="line-117"></span><span class="hs-comment">-- to restrict Key a ~ Key b.  We provide our own mapping</span><span>
</span><span id="line-118"></span><span class="hs-comment">-- functions.</span><span>
</span><span id="line-119"></span><span>
</span><span id="line-120"></span><span class="hs-comment">-- General strategy is most operations are deferred to the</span><span>
</span><span id="line-121"></span><span class="hs-comment">-- Map representation.</span><span>
</span><span id="line-122"></span><span>
</span><span id="line-123"></span><span id="local-6989586621679651226"><span class="hs-keyword">instance</span><span> </span><span id="local-6989586621679650908"><span id="local-6989586621679650911"><span class="annot"><a href="../../base/src/GHC.Show.html#Show"><span class="hs-identifier hs-type">Show</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651226"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Show.html#Show"><span class="hs-identifier hs-type">Show</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651226"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span></span></span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-124"></span><span>    </span><span id="local-6989586621679650904"><span class="annot"><span class="annottext">show :: Graph a -&gt; String
</span><a href="../../base/src/GHC.Show.html#show"><span class="hs-identifier hs-var hs-var hs-var hs-var">show</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[a] -&gt; String
forall a. Show a =&gt; a -&gt; String
</span><a href="../../base/src/GHC.Show.html#show"><span class="hs-identifier hs-var">show</span></a></span><span> </span><span class="annot"><span class="annottext">([a] -&gt; String) -&gt; (Graph a -&gt; [a]) -&gt; Graph a -&gt; String
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a -&gt; [a]
forall a. Graph a -&gt; [a]
</span><a href="Distribution.Compat.Graph.html#toList"><span class="hs-identifier hs-var">toList</span></a></span></span><span>
</span><span id="line-125"></span><span>
</span><span id="line-126"></span><span id="local-6989586621679651217"><span class="hs-keyword">instance</span><span> </span><span id="local-6989586621679650895"><span id="local-6989586621679650897"><span id="local-6989586621679650899"><span class="hs-special">(</span><span class="annot"><a href="Distribution.Compat.Graph.html#IsNode"><span class="hs-identifier hs-type">IsNode</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651217"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../base/src/GHC.Read.html#Read"><span class="hs-identifier hs-type">Read</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651217"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../base/src/GHC.Show.html#Show"><span class="hs-identifier hs-type">Show</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651217"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Read.html#Read"><span class="hs-identifier hs-type">Read</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651217"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span></span></span></span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-127"></span><span>    </span><span id="local-6989586621679650889"><span class="annot"><span class="annottext">readsPrec :: Vertex -&gt; ReadS (Graph a)
</span><a href="../../base/src/GHC.Read.html#readsPrec"><span class="hs-identifier hs-var hs-var hs-var hs-var">readsPrec</span></a></span></span><span> </span><span id="local-6989586621679650887"><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621679650887"><span class="hs-identifier hs-var">d</span></a></span></span><span> </span><span id="local-6989586621679650886"><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679650886"><span class="hs-identifier hs-var">s</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(([a], String) -&gt; (Graph a, String))
-&gt; [([a], String)] -&gt; [(Graph a, String)]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-glyph">\</span><span class="hs-special">(</span><span id="local-6989586621679650885"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621679650885"><span class="hs-identifier hs-var">a</span></a></span></span><span class="hs-special">,</span><span id="local-6989586621679650884"><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679650884"><span class="hs-identifier hs-var">r</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">[a] -&gt; Graph a
forall a. (IsNode a, Show (Key a)) =&gt; [a] -&gt; Graph a
</span><a href="Distribution.Compat.Graph.html#fromDistinctList"><span class="hs-identifier hs-var">fromDistinctList</span></a></span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621679650885"><span class="hs-identifier hs-var">a</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679650884"><span class="hs-identifier hs-var">r</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Vertex -&gt; ReadS [a]
forall a. Read a =&gt; Vertex -&gt; ReadS a
</span><a href="../../base/src/GHC.Read.html#readsPrec"><span class="hs-identifier hs-var">readsPrec</span></a></span><span> </span><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621679650887"><span class="hs-identifier hs-var">d</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><a href="#local-6989586621679650886"><span class="hs-identifier hs-var">s</span></a></span><span class="hs-special">)</span></span><span>
</span><span id="line-128"></span><span>
</span><span id="line-129"></span><span id="local-6989586621679651209"><span class="hs-keyword">instance</span><span> </span><span id="local-6989586621679650880"><span class="hs-special">(</span><span class="annot"><a href="Distribution.Compat.Graph.html#IsNode"><span class="hs-identifier hs-type">IsNode</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651209"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../binary/src/Data.Binary.Class.html#Binary"><span class="hs-identifier hs-type">Binary</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651209"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../base/src/GHC.Show.html#Show"><span class="hs-identifier hs-type">Show</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651209"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="../../binary/src/Data.Binary.Class.html#Binary"><span class="hs-identifier hs-type">Binary</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651209"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span></span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-130"></span><span>    </span><span id="local-6989586621679650876"><span class="annot"><span class="annottext">put :: Graph a -&gt; Put
</span><a href="../../binary/src/Data.Binary.Class.html#put"><span class="hs-identifier hs-var hs-var hs-var hs-var">put</span></a></span></span><span> </span><span id="local-6989586621679650874"><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650874"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[a] -&gt; Put
forall t. Binary t =&gt; t -&gt; Put
</span><a href="../../binary/src/Data.Binary.Class.html#put"><span class="hs-identifier hs-var">put</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; [a]
forall a. Graph a -&gt; [a]
</span><a href="Distribution.Compat.Graph.html#toList"><span class="hs-identifier hs-var">toList</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650874"><span class="hs-identifier hs-var">x</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-131"></span><span>    </span><span id="local-6989586621679650868"><span class="annot"><span class="annottext">get :: Get (Graph a)
</span><a href="../../binary/src/Data.Binary.Class.html#get"><span class="hs-identifier hs-var hs-var hs-var hs-var">get</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">([a] -&gt; Graph a) -&gt; Get [a] -&gt; Get (Graph a)
forall (f :: * -&gt; *) a b. Functor f =&gt; (a -&gt; b) -&gt; f a -&gt; f b
</span><a href="../../base/src/GHC.Base.html#fmap"><span class="hs-identifier hs-var">fmap</span></a></span><span> </span><span class="annot"><span class="annottext">[a] -&gt; Graph a
forall a. (IsNode a, Show (Key a)) =&gt; [a] -&gt; Graph a
</span><a href="Distribution.Compat.Graph.html#fromDistinctList"><span class="hs-identifier hs-var">fromDistinctList</span></a></span><span> </span><span class="annot"><span class="annottext">Get [a]
forall t. Binary t =&gt; Get t
</span><a href="../../binary/src/Data.Binary.Class.html#get"><span class="hs-identifier hs-var">get</span></a></span></span><span>
</span><span id="line-132"></span><span>
</span><span id="line-133"></span><span id="local-6989586621679651199"><span class="hs-keyword">instance</span><span> </span><span id="local-6989586621679650861"><span class="annot"><a href="Distribution.Utils.Structured.html#Structured"><span class="hs-identifier hs-type">Structured</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651199"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="Distribution.Utils.Structured.html#Structured"><span class="hs-identifier hs-type">Structured</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651199"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span></span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-134"></span><span>    </span><span id="local-6989586621679650854"><span class="annot"><span class="annottext">structure :: Proxy (Graph a) -&gt; Structure
</span><a href="Distribution.Utils.Structured.html#structure"><span class="hs-identifier hs-var hs-var hs-var hs-var">structure</span></a></span></span><span> </span><span id="local-6989586621679650852"><span class="annot"><span class="annottext">Proxy (Graph a)
</span><a href="#local-6989586621679650852"><span class="hs-identifier hs-var">p</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">TypeRep -&gt; TypeVersion -&gt; String -&gt; [Structure] -&gt; Structure
</span><a href="Distribution.Utils.Structured.html#Nominal"><span class="hs-identifier hs-var">Nominal</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Proxy (Graph a) -&gt; TypeRep
forall {k} (proxy :: k -&gt; *) (a :: k).
Typeable a =&gt;
proxy a -&gt; TypeRep
</span><a href="../../base/src/Data.Typeable.html#typeRep"><span class="hs-identifier hs-var">typeRep</span></a></span><span> </span><span class="annot"><span class="annottext">Proxy (Graph a)
</span><a href="#local-6989586621679650852"><span class="hs-identifier hs-var">p</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">TypeVersion
</span><span class="hs-number">0</span></span><span> </span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;Graph&quot;</span></span><span> </span><span class="hs-special">[</span><span class="annot"><span class="annottext">Proxy a -&gt; Structure
forall a. Structured a =&gt; Proxy a -&gt; Structure
</span><a href="Distribution.Utils.Structured.html#structure"><span class="hs-identifier hs-var">structure</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Proxy a
forall {k} (t :: k). Proxy t
</span><a href="../../base/src/Data.Proxy.html#Proxy"><span class="hs-identifier hs-var">Proxy</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="../../base/src/Data.Proxy.html#Proxy"><span class="hs-identifier hs-type">Proxy</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651199"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span class="hs-special">]</span></span><span>
</span><span id="line-135"></span><span>
</span><span id="line-136"></span><span id="local-6989586621679651190"><span class="hs-keyword">instance</span><span> </span><span id="local-6989586621679650846"><span class="hs-special">(</span><span class="annot"><span class="hs-identifier hs-type">Eq</span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651190"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span class="hs-special">,</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Eq</span></span><span> </span><span class="annot"><a href="#local-6989586621679651190"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Eq</span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651190"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span></span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-137"></span><span>    </span><span id="local-6989586621679650842"><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650842"><span class="hs-identifier hs-var">g1</span></a></span></span><span> </span><span id="local-6989586621679650841"><span class="annot"><span class="annottext">== :: Graph a -&gt; Graph a -&gt; Bool
</span><span class="hs-operator hs-var hs-var hs-var hs-var">==</span></span></span><span> </span><span id="local-6989586621679650840"><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650840"><span class="hs-identifier hs-var">g2</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#graphMap"><span class="hs-identifier hs-var hs-var">graphMap</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650842"><span class="hs-identifier hs-var">g1</span></a></span><span> </span><span class="annot"><span class="annottext">Map (Key a) a -&gt; Map (Key a) a -&gt; Bool
forall a. Eq a =&gt; a -&gt; a -&gt; Bool
</span><span class="hs-operator hs-var">==</span></span><span> </span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#graphMap"><span class="hs-identifier hs-var hs-var">graphMap</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650840"><span class="hs-identifier hs-var">g2</span></a></span></span><span>
</span><span id="line-138"></span><span>
</span><span id="line-139"></span><span class="hs-keyword">instance</span><span> </span><span id="local-6989586621679650828"><span id="local-6989586621679650830"><span id="local-6989586621679650836"><span class="annot"><a href="../../base/src/Data.Foldable.html#Foldable"><span class="hs-identifier hs-type">Foldable.Foldable</span></a></span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span></span></span></span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-140"></span><span>    </span><span id="local-6989586621679650814"><span class="annot"><span class="annottext">fold :: forall m. Monoid m =&gt; Graph m -&gt; m
</span><a href="../../base/src/Data.Foldable.html#fold"><span class="hs-identifier hs-var hs-var hs-var hs-var">fold</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Map (Key m) m -&gt; m
forall (t :: * -&gt; *) m. (Foldable t, Monoid m) =&gt; t m -&gt; m
</span><a href="../../base/src/Data.Foldable.html#fold"><span class="hs-identifier hs-var">Foldable.fold</span></a></span><span> </span><span class="annot"><span class="annottext">(Map (Key m) m -&gt; m) -&gt; (Graph m -&gt; Map (Key m) m) -&gt; Graph m -&gt; m
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">Graph m -&gt; Map (Key m) m
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#graphMap"><span class="hs-identifier hs-var hs-var">graphMap</span></a></span><span>
</span><span id="line-141"></span><span>    </span><span id="local-6989586621679650811"><span class="annot"><span class="annottext">foldr :: forall a b. (a -&gt; b -&gt; b) -&gt; b -&gt; Graph a -&gt; b
</span><a href="../../base/src/Data.Foldable.html#foldr"><span class="hs-identifier hs-var hs-var hs-var hs-var">foldr</span></a></span></span><span> </span><span id="local-6989586621679650809"><span class="annot"><span class="annottext">a -&gt; b -&gt; b
</span><a href="#local-6989586621679650809"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span id="local-6989586621679650808"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679650808"><span class="hs-identifier hs-var">z</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(a -&gt; b -&gt; b) -&gt; b -&gt; Map (Key a) a -&gt; b
forall (t :: * -&gt; *) a b.
Foldable t =&gt;
(a -&gt; b -&gt; b) -&gt; b -&gt; t a -&gt; b
</span><a href="../../base/src/Data.Foldable.html#foldr"><span class="hs-identifier hs-var">Foldable.foldr</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; b -&gt; b
</span><a href="#local-6989586621679650809"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679650808"><span class="hs-identifier hs-var">z</span></a></span><span> </span><span class="annot"><span class="annottext">(Map (Key a) a -&gt; b) -&gt; (Graph a -&gt; Map (Key a) a) -&gt; Graph a -&gt; b
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#graphMap"><span class="hs-identifier hs-var hs-var">graphMap</span></a></span><span>
</span><span id="line-142"></span><span>    </span><span id="local-6989586621679650806"><span class="annot"><span class="annottext">foldl :: forall b a. (b -&gt; a -&gt; b) -&gt; b -&gt; Graph a -&gt; b
</span><a href="../../base/src/Data.Foldable.html#foldl"><span class="hs-identifier hs-var hs-var hs-var hs-var">foldl</span></a></span></span><span> </span><span id="local-6989586621679650804"><span class="annot"><span class="annottext">b -&gt; a -&gt; b
</span><a href="#local-6989586621679650804"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span id="local-6989586621679650803"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679650803"><span class="hs-identifier hs-var">z</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(b -&gt; a -&gt; b) -&gt; b -&gt; Map (Key a) a -&gt; b
forall (t :: * -&gt; *) b a.
Foldable t =&gt;
(b -&gt; a -&gt; b) -&gt; b -&gt; t a -&gt; b
</span><a href="../../base/src/Data.Foldable.html#foldl"><span class="hs-identifier hs-var">Foldable.foldl</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; a -&gt; b
</span><a href="#local-6989586621679650804"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679650803"><span class="hs-identifier hs-var">z</span></a></span><span> </span><span class="annot"><span class="annottext">(Map (Key a) a -&gt; b) -&gt; (Graph a -&gt; Map (Key a) a) -&gt; Graph a -&gt; b
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#graphMap"><span class="hs-identifier hs-var hs-var">graphMap</span></a></span><span>
</span><span id="line-143"></span><span>    </span><span id="local-6989586621679650799"><span class="annot"><span class="annottext">foldMap :: forall m a. Monoid m =&gt; (a -&gt; m) -&gt; Graph a -&gt; m
</span><a href="../../base/src/Data.Foldable.html#foldMap"><span class="hs-identifier hs-var hs-var hs-var hs-var">foldMap</span></a></span></span><span> </span><span id="local-6989586621679650797"><span class="annot"><span class="annottext">a -&gt; m
</span><a href="#local-6989586621679650797"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(a -&gt; m) -&gt; Map (Key a) a -&gt; m
forall (t :: * -&gt; *) m a.
(Foldable t, Monoid m) =&gt;
(a -&gt; m) -&gt; t a -&gt; m
</span><a href="../../base/src/Data.Foldable.html#foldMap"><span class="hs-identifier hs-var">Foldable.foldMap</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; m
</span><a href="#local-6989586621679650797"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">(Map (Key a) a -&gt; m) -&gt; (Graph a -&gt; Map (Key a) a) -&gt; Graph a -&gt; m
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#graphMap"><span class="hs-identifier hs-var hs-var">graphMap</span></a></span><span>
</span><span id="line-144"></span><span>    </span><span id="local-6989586621679650795"><span class="annot"><span class="annottext">foldl' :: forall b a. (b -&gt; a -&gt; b) -&gt; b -&gt; Graph a -&gt; b
</span><a href="../../base/src/Data.Foldable.html#foldl%27"><span class="hs-identifier hs-var hs-var hs-var hs-var">foldl'</span></a></span></span><span> </span><span id="local-6989586621679650793"><span class="annot"><span class="annottext">b -&gt; a -&gt; b
</span><a href="#local-6989586621679650793"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span id="local-6989586621679650792"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679650792"><span class="hs-identifier hs-var">z</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(b -&gt; a -&gt; b) -&gt; b -&gt; Map (Key a) a -&gt; b
forall (t :: * -&gt; *) b a.
Foldable t =&gt;
(b -&gt; a -&gt; b) -&gt; b -&gt; t a -&gt; b
</span><a href="../../base/src/Data.Foldable.html#foldl%27"><span class="hs-identifier hs-var">Foldable.foldl'</span></a></span><span> </span><span class="annot"><span class="annottext">b -&gt; a -&gt; b
</span><a href="#local-6989586621679650793"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679650792"><span class="hs-identifier hs-var">z</span></a></span><span> </span><span class="annot"><span class="annottext">(Map (Key a) a -&gt; b) -&gt; (Graph a -&gt; Map (Key a) a) -&gt; Graph a -&gt; b
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#graphMap"><span class="hs-identifier hs-var hs-var">graphMap</span></a></span><span>
</span><span id="line-145"></span><span>    </span><span id="local-6989586621679650790"><span class="annot"><span class="annottext">foldr' :: forall a b. (a -&gt; b -&gt; b) -&gt; b -&gt; Graph a -&gt; b
</span><a href="../../base/src/Data.Foldable.html#foldr%27"><span class="hs-identifier hs-var hs-var hs-var hs-var">foldr'</span></a></span></span><span> </span><span id="local-6989586621679650788"><span class="annot"><span class="annottext">a -&gt; b -&gt; b
</span><a href="#local-6989586621679650788"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span id="local-6989586621679650787"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679650787"><span class="hs-identifier hs-var">z</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(a -&gt; b -&gt; b) -&gt; b -&gt; Map (Key a) a -&gt; b
forall (t :: * -&gt; *) a b.
Foldable t =&gt;
(a -&gt; b -&gt; b) -&gt; b -&gt; t a -&gt; b
</span><a href="../../base/src/Data.Foldable.html#foldr%27"><span class="hs-identifier hs-var">Foldable.foldr'</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; b -&gt; b
</span><a href="#local-6989586621679650788"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679650787"><span class="hs-identifier hs-var">z</span></a></span><span> </span><span class="annot"><span class="annottext">(Map (Key a) a -&gt; b) -&gt; (Graph a -&gt; Map (Key a) a) -&gt; Graph a -&gt; b
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#graphMap"><span class="hs-identifier hs-var hs-var">graphMap</span></a></span><span class="hs-cpp">
#ifdef MIN_VERSION_base
</span><span class="hs-cpp">#if MIN_VERSION_base(4,8,0)
</span><span>    </span><span id="local-6989586621679650785"><span class="annot"><span class="annottext">length :: forall a. Graph a -&gt; Vertex
</span><a href="../../base/src/Data.Foldable.html#length"><span class="hs-identifier hs-var hs-var hs-var hs-var">length</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Map (Key a) a -&gt; Vertex
forall (t :: * -&gt; *) a. Foldable t =&gt; t a -&gt; Vertex
</span><a href="../../base/src/Data.Foldable.html#length"><span class="hs-identifier hs-var">Foldable.length</span></a></span><span> </span><span class="annot"><span class="annottext">(Map (Key a) a -&gt; Vertex)
-&gt; (Graph a -&gt; Map (Key a) a) -&gt; Graph a -&gt; Vertex
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#graphMap"><span class="hs-identifier hs-var hs-var">graphMap</span></a></span><span>
</span><span id="line-149"></span><span>    </span><span id="local-6989586621679650782"><span class="annot"><span class="annottext">null :: forall a. Graph a -&gt; Bool
</span><a href="#local-6989586621679650782"><span class="hs-identifier hs-var hs-var hs-var hs-var">null</span></a></span></span><span>   </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Map (Key a) a -&gt; Bool
forall (t :: * -&gt; *) a. Foldable t =&gt; t a -&gt; Bool
</span><a href="../../base/src/Data.Foldable.html#null"><span class="hs-identifier hs-var">Foldable.null</span></a></span><span>   </span><span class="annot"><span class="annottext">(Map (Key a) a -&gt; Bool)
-&gt; (Graph a -&gt; Map (Key a) a) -&gt; Graph a -&gt; Bool
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#graphMap"><span class="hs-identifier hs-var hs-var">graphMap</span></a></span><span>
</span><span id="line-150"></span><span>    </span><span id="local-6989586621679650780"><span class="annot"><span class="annottext">toList :: forall a. Graph a -&gt; [a]
</span><a href="#local-6989586621679650780"><span class="hs-identifier hs-var hs-var hs-var hs-var">toList</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Map (Key a) a -&gt; [a]
forall (t :: * -&gt; *) a. Foldable t =&gt; t a -&gt; [a]
</span><a href="../../base/src/Data.Foldable.html#toList"><span class="hs-identifier hs-var">Foldable.toList</span></a></span><span> </span><span class="annot"><span class="annottext">(Map (Key a) a -&gt; [a])
-&gt; (Graph a -&gt; Map (Key a) a) -&gt; Graph a -&gt; [a]
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#graphMap"><span class="hs-identifier hs-var hs-var">graphMap</span></a></span><span>
</span><span id="line-151"></span><span>    </span><span id="local-6989586621679650776"><span class="annot"><span class="annottext">elem :: forall a. Eq a =&gt; a -&gt; Graph a -&gt; Bool
</span><a href="../../base/src/Data.Foldable.html#elem"><span class="hs-identifier hs-var hs-var hs-var hs-var">elem</span></a></span></span><span> </span><span id="local-6989586621679650774"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679650774"><span class="hs-identifier hs-var">x</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a -&gt; Map (Key a) a -&gt; Bool
forall (t :: * -&gt; *) a. (Foldable t, Eq a) =&gt; a -&gt; t a -&gt; Bool
</span><a href="../../base/src/Data.Foldable.html#elem"><span class="hs-identifier hs-var">Foldable.elem</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679650774"><span class="hs-identifier hs-var">x</span></a></span><span> </span><span class="annot"><span class="annottext">(Map (Key a) a -&gt; Bool)
-&gt; (Graph a -&gt; Map (Key a) a) -&gt; Graph a -&gt; Bool
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#graphMap"><span class="hs-identifier hs-var hs-var">graphMap</span></a></span><span>
</span><span id="line-152"></span><span>    </span><span id="local-6989586621679650770"><span class="annot"><span class="annottext">maximum :: forall a. Ord a =&gt; Graph a -&gt; a
</span><a href="../../base/src/Data.Foldable.html#maximum"><span class="hs-identifier hs-var hs-var hs-var hs-var">maximum</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Map (Key a) a -&gt; a
forall (t :: * -&gt; *) a. (Foldable t, Ord a) =&gt; t a -&gt; a
</span><a href="../../base/src/Data.Foldable.html#maximum"><span class="hs-identifier hs-var">Foldable.maximum</span></a></span><span> </span><span class="annot"><span class="annottext">(Map (Key a) a -&gt; a) -&gt; (Graph a -&gt; Map (Key a) a) -&gt; Graph a -&gt; a
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#graphMap"><span class="hs-identifier hs-var hs-var">graphMap</span></a></span><span>
</span><span id="line-153"></span><span>    </span><span id="local-6989586621679650765"><span class="annot"><span class="annottext">minimum :: forall a. Ord a =&gt; Graph a -&gt; a
</span><a href="../../base/src/Data.Foldable.html#minimum"><span class="hs-identifier hs-var hs-var hs-var hs-var">minimum</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Map (Key a) a -&gt; a
forall (t :: * -&gt; *) a. (Foldable t, Ord a) =&gt; t a -&gt; a
</span><a href="../../base/src/Data.Foldable.html#minimum"><span class="hs-identifier hs-var">Foldable.minimum</span></a></span><span> </span><span class="annot"><span class="annottext">(Map (Key a) a -&gt; a) -&gt; (Graph a -&gt; Map (Key a) a) -&gt; Graph a -&gt; a
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#graphMap"><span class="hs-identifier hs-var hs-var">graphMap</span></a></span><span>
</span><span id="line-154"></span><span>    </span><span id="local-6989586621679650760"><span class="annot"><span class="annottext">sum :: forall a. Num a =&gt; Graph a -&gt; a
</span><a href="../../base/src/Data.Foldable.html#sum"><span class="hs-identifier hs-var hs-var hs-var hs-var">sum</span></a></span></span><span>     </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Map (Key a) a -&gt; a
forall (t :: * -&gt; *) a. (Foldable t, Num a) =&gt; t a -&gt; a
</span><a href="../../base/src/Data.Foldable.html#sum"><span class="hs-identifier hs-var">Foldable.sum</span></a></span><span>     </span><span class="annot"><span class="annottext">(Map (Key a) a -&gt; a) -&gt; (Graph a -&gt; Map (Key a) a) -&gt; Graph a -&gt; a
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#graphMap"><span class="hs-identifier hs-var hs-var">graphMap</span></a></span><span>
</span><span id="line-155"></span><span>    </span><span id="local-6989586621679650755"><span class="annot"><span class="annottext">product :: forall a. Num a =&gt; Graph a -&gt; a
</span><a href="../../base/src/Data.Foldable.html#product"><span class="hs-identifier hs-var hs-var hs-var hs-var">product</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Map (Key a) a -&gt; a
forall (t :: * -&gt; *) a. (Foldable t, Num a) =&gt; t a -&gt; a
</span><a href="../../base/src/Data.Foldable.html#product"><span class="hs-identifier hs-var">Foldable.product</span></a></span><span> </span><span class="annot"><span class="annottext">(Map (Key a) a -&gt; a) -&gt; (Graph a -&gt; Map (Key a) a) -&gt; Graph a -&gt; a
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#graphMap"><span class="hs-identifier hs-var hs-var">graphMap</span></a></span><span class="hs-cpp">
#endif
</span><span class="hs-cpp">#endif
</span><span>
</span><span id="line-159"></span><span id="local-6989586621679651149"><span class="hs-keyword">instance</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../deepseq/src/Control.DeepSeq.html#NFData"><span class="hs-identifier hs-type">NFData</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651149"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../deepseq/src/Control.DeepSeq.html#NFData"><span class="hs-identifier hs-type">NFData</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651149"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="../../deepseq/src/Control.DeepSeq.html#NFData"><span class="hs-identifier hs-type">NFData</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651149"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-160"></span><span>    </span><span id="local-6989586621679650745"><span class="annot"><span class="annottext">rnf :: Graph a -&gt; ()
</span><a href="../../deepseq/src/Control.DeepSeq.html#rnf"><span class="hs-identifier hs-var hs-var hs-var hs-var">rnf</span></a></span></span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="hs-special">{</span><span>
</span><span id="line-161"></span><span>        </span><span class="annot"><span class="annottext">graphMap :: forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#graphMap"><span class="hs-identifier hs-var">graphMap</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span id="local-6989586621679650743"><span class="annot"><span class="annottext">Map (Key a) a
</span><a href="#local-6989586621679650743"><span class="hs-identifier hs-var">m</span></a></span></span><span class="hs-special">,</span><span>
</span><span id="line-162"></span><span>        </span><span class="annot"><span class="annottext">graphForward :: forall a. Graph a -&gt; Graph
</span><a href="Distribution.Compat.Graph.html#graphForward"><span class="hs-identifier hs-var">graphForward</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span id="local-6989586621679650742"><span class="annot"><span class="annottext">Graph
</span><a href="#local-6989586621679650742"><span class="hs-identifier hs-var">gf</span></a></span></span><span class="hs-special">,</span><span>
</span><span id="line-163"></span><span>        </span><span class="annot"><span class="annottext">graphAdjoint :: forall a. Graph a -&gt; Graph
</span><a href="Distribution.Compat.Graph.html#graphAdjoint"><span class="hs-identifier hs-var">graphAdjoint</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span id="local-6989586621679650741"><span class="annot"><span class="annottext">Graph
</span><a href="#local-6989586621679650741"><span class="hs-identifier hs-var">ga</span></a></span></span><span class="hs-special">,</span><span>
</span><span id="line-164"></span><span>        </span><span class="annot"><span class="annottext">graphVertexToNode :: forall a. Graph a -&gt; Vertex -&gt; a
</span><a href="Distribution.Compat.Graph.html#graphVertexToNode"><span class="hs-identifier hs-var">graphVertexToNode</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span id="local-6989586621679650740"><span class="annot"><span class="annottext">Vertex -&gt; a
</span><a href="#local-6989586621679650740"><span class="hs-identifier hs-var">vtn</span></a></span></span><span class="hs-special">,</span><span>
</span><span id="line-165"></span><span>        </span><span class="annot"><span class="annottext">graphKeyToVertex :: forall a. Graph a -&gt; Key a -&gt; Maybe Vertex
</span><a href="Distribution.Compat.Graph.html#graphKeyToVertex"><span class="hs-identifier hs-var">graphKeyToVertex</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span id="local-6989586621679650739"><span class="annot"><span class="annottext">Key a -&gt; Maybe Vertex
</span><a href="#local-6989586621679650739"><span class="hs-identifier hs-var">ktv</span></a></span></span><span class="hs-special">,</span><span>
</span><span id="line-166"></span><span>        </span><span class="annot"><span class="annottext">graphBroken :: forall a. Graph a -&gt; [(a, [Key a])]
</span><a href="Distribution.Compat.Graph.html#graphBroken"><span class="hs-identifier hs-var">graphBroken</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span id="local-6989586621679650738"><span class="annot"><span class="annottext">[(a, [Key a])]
</span><a href="#local-6989586621679650738"><span class="hs-identifier hs-var">b</span></a></span></span><span>
</span><span id="line-167"></span><span>    </span><span class="hs-special">}</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Graph
</span><a href="#local-6989586621679650742"><span class="hs-identifier hs-var">gf</span></a></span><span> </span><span class="annot"><span class="annottext">Graph -&gt; () -&gt; ()
</span><span class="hs-operator hs-var">`seq`</span></span><span> </span><span class="annot"><span class="annottext">Graph
</span><a href="#local-6989586621679650741"><span class="hs-identifier hs-var">ga</span></a></span><span> </span><span class="annot"><span class="annottext">Graph -&gt; () -&gt; ()
</span><span class="hs-operator hs-var">`seq`</span></span><span> </span><span class="annot"><span class="annottext">Vertex -&gt; a
</span><a href="#local-6989586621679650740"><span class="hs-identifier hs-var">vtn</span></a></span><span> </span><span class="annot"><span class="annottext">(Vertex -&gt; a) -&gt; () -&gt; ()
</span><span class="hs-operator hs-var">`seq`</span></span><span> </span><span class="annot"><span class="annottext">Key a -&gt; Maybe Vertex
</span><a href="#local-6989586621679650739"><span class="hs-identifier hs-var">ktv</span></a></span><span> </span><span class="annot"><span class="annottext">(Key a -&gt; Maybe Vertex) -&gt; () -&gt; ()
</span><span class="hs-operator hs-var">`seq`</span></span><span> </span><span class="annot"><span class="annottext">[(a, [Key a])]
</span><a href="#local-6989586621679650738"><span class="hs-identifier hs-var">b</span></a></span><span> </span><span class="annot"><span class="annottext">[(a, [Key a])] -&gt; () -&gt; ()
</span><span class="hs-operator hs-var">`seq`</span></span><span> </span><span class="annot"><span class="annottext">Map (Key a) a -&gt; ()
forall a. NFData a =&gt; a -&gt; ()
</span><a href="../../deepseq/src/Control.DeepSeq.html#rnf"><span class="hs-identifier hs-var">rnf</span></a></span><span> </span><span class="annot"><span class="annottext">Map (Key a) a
</span><a href="#local-6989586621679650743"><span class="hs-identifier hs-var">m</span></a></span></span><span>
</span><span id="line-168"></span><span>
</span><span id="line-169"></span><span class="hs-comment">-- TODO: Data instance?</span><span>
</span><span id="line-170"></span><span>
</span><span id="line-171"></span><span class="hs-comment">-- | The 'IsNode' class is used for datatypes which represent directed</span><span>
</span><span id="line-172"></span><span class="hs-comment">-- graph nodes.  A node of type @a@ is associated with some unique key of</span><span>
</span><span id="line-173"></span><span class="hs-comment">-- type @'Key' a@; given a node we can determine its key ('nodeKey')</span><span>
</span><span id="line-174"></span><span class="hs-comment">-- and the keys of its neighbors ('nodeNeighbors').</span><span>
</span><span id="line-175"></span><span class="hs-keyword">class</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ord</span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651143"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span id="IsNode"><span class="annot"><a href="Distribution.Compat.Graph.html#IsNode"><span class="hs-identifier hs-var">IsNode</span></a></span></span><span> </span><span id="local-6989586621679651143"><span class="annot"><a href="#local-6989586621679651143"><span class="hs-identifier hs-type">a</span></a></span></span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-176"></span><span>    </span><span class="hs-keyword">type</span><span> </span><span id="Key"><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-var">Key</span></a></span></span><span> </span><span id="local-6989586621679651143"><span class="annot"><a href="#local-6989586621679651143"><span class="hs-identifier hs-type">a</span></a></span></span><span>
</span><span id="line-177"></span><span>    </span><span id="nodeKey"><span class="annot"><a href="Distribution.Compat.Graph.html#nodeKey"><span class="hs-identifier hs-type">nodeKey</span></a></span></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="#local-6989586621679651143"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651143"><span class="hs-identifier hs-type">a</span></a></span><span>
</span><span id="line-178"></span><span>    </span><span id="nodeNeighbors"><span class="annot"><a href="Distribution.Compat.Graph.html#nodeNeighbors"><span class="hs-identifier hs-type">nodeNeighbors</span></a></span></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="#local-6989586621679651143"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651143"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span>
</span><span id="line-179"></span><span>
</span><span id="line-180"></span><span id="local-6989586621679651139"><span id="local-6989586621679651140"><span class="hs-keyword">instance</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Compat.Graph.html#IsNode"><span class="hs-identifier hs-type">IsNode</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651140"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#IsNode"><span class="hs-identifier hs-type">IsNode</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651139"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651140"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="annot"><span class="hs-operator hs-type">~</span></span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651139"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#IsNode"><span class="hs-identifier hs-type">IsNode</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../base/src/Data.Either.html#Either"><span class="hs-identifier hs-type">Either</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651140"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651139"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-181"></span><span>    </span><span class="hs-keyword">type</span><span> </span><span id="Key"><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-var">Key</span></a></span></span><span> </span><span id="local-6989586621679651139"><span id="local-6989586621679651140"><span class="hs-special">(</span><span class="annot"><a href="../../base/src/Data.Either.html#Either"><span class="hs-identifier hs-type">Either</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651140"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651139"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651140"><span class="hs-identifier hs-type">a</span></a></span><span>
</span><span id="line-182"></span><span>    </span><span id="local-6989586621679650717"><span class="annot"><span class="annottext">nodeKey :: Either a b -&gt; Key (Either a b)
</span><a href="#local-6989586621679650717"><span class="hs-identifier hs-var hs-var hs-var hs-var">nodeKey</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../base/src/Data.Either.html#Left"><span class="hs-identifier hs-type">Left</span></a></span><span> </span><span id="local-6989586621679650716"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679650716"><span class="hs-identifier hs-var">x</span></a></span></span><span class="hs-special">)</span><span>  </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a -&gt; Key a
forall a. IsNode a =&gt; a -&gt; Key a
</span><a href="Distribution.Compat.Graph.html#nodeKey"><span class="hs-identifier hs-var">nodeKey</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679650716"><span class="hs-identifier hs-var">x</span></a></span><span>
</span><span id="line-183"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#nodeKey"><span class="hs-identifier hs-var">nodeKey</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../base/src/Data.Either.html#Right"><span class="hs-identifier hs-type">Right</span></a></span><span> </span><span id="local-6989586621679650715"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679650715"><span class="hs-identifier hs-var">x</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">b -&gt; Key b
forall a. IsNode a =&gt; a -&gt; Key a
</span><a href="Distribution.Compat.Graph.html#nodeKey"><span class="hs-identifier hs-var">nodeKey</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679650715"><span class="hs-identifier hs-var">x</span></a></span><span>
</span><span id="line-184"></span><span>    </span><span id="local-6989586621679650712"><span class="annot"><span class="annottext">nodeNeighbors :: Either a b -&gt; [Key (Either a b)]
</span><a href="#local-6989586621679650712"><span class="hs-identifier hs-var hs-var hs-var hs-var">nodeNeighbors</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../base/src/Data.Either.html#Left"><span class="hs-identifier hs-type">Left</span></a></span><span> </span><span id="local-6989586621679650711"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679650711"><span class="hs-identifier hs-var">x</span></a></span></span><span class="hs-special">)</span><span>  </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a -&gt; [Key a]
forall a. IsNode a =&gt; a -&gt; [Key a]
</span><a href="Distribution.Compat.Graph.html#nodeNeighbors"><span class="hs-identifier hs-var">nodeNeighbors</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679650711"><span class="hs-identifier hs-var">x</span></a></span><span>
</span><span id="line-185"></span><span>    </span><span class="annot"><a href="Distribution.Compat.Graph.html#nodeNeighbors"><span class="hs-identifier hs-var">nodeNeighbors</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../base/src/Data.Either.html#Right"><span class="hs-identifier hs-type">Right</span></a></span><span> </span><span id="local-6989586621679650710"><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679650710"><span class="hs-identifier hs-var">x</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">b -&gt; [Key b]
forall a. IsNode a =&gt; a -&gt; [Key a]
</span><a href="Distribution.Compat.Graph.html#nodeNeighbors"><span class="hs-identifier hs-var">nodeNeighbors</span></a></span><span> </span><span class="annot"><span class="annottext">b
</span><a href="#local-6989586621679650710"><span class="hs-identifier hs-var">x</span></a></span></span></span><span>
</span><span id="line-186"></span><span>
</span><span id="line-187"></span><span class="hs-comment">-- | A simple, trivial data type which admits an 'IsNode' instance.</span><span>
</span><span id="line-188"></span><span class="hs-keyword">data</span><span> </span><span id="Node"><span class="annot"><a href="Distribution.Compat.Graph.html#Node"><span class="hs-identifier hs-var">Node</span></a></span></span><span> </span><span id="local-6989586621679651137"><span class="annot"><a href="#local-6989586621679651137"><span class="hs-identifier hs-type">k</span></a></span></span><span> </span><span id="local-6989586621679651138"><span class="annot"><a href="#local-6989586621679651138"><span class="hs-identifier hs-type">a</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span id="N"><span class="annot"><a href="Distribution.Compat.Graph.html#N"><span class="hs-identifier hs-var">N</span></a></span></span><span> </span><span class="annot"><a href="#local-6989586621679651138"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651137"><span class="hs-identifier hs-type">k</span></a></span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679651137"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">]</span><span>
</span><span id="line-189"></span><span>    </span><span class="hs-keyword">deriving</span><span> </span><span class="hs-special">(</span><span id="local-6989586621679650698"><span id="local-6989586621679650700"><span id="local-6989586621679650707"><span class="annot"><span class="annottext">Vertex -&gt; Node k a -&gt; ShowS
[Node k a] -&gt; ShowS
Node k a -&gt; String
(Vertex -&gt; Node k a -&gt; ShowS)
-&gt; (Node k a -&gt; String) -&gt; ([Node k a] -&gt; ShowS) -&gt; Show (Node k a)
forall a.
(Vertex -&gt; a -&gt; ShowS) -&gt; (a -&gt; String) -&gt; ([a] -&gt; ShowS) -&gt; Show a
forall k a. (Show a, Show k) =&gt; Vertex -&gt; Node k a -&gt; ShowS
forall k a. (Show a, Show k) =&gt; [Node k a] -&gt; ShowS
forall k a. (Show a, Show k) =&gt; Node k a -&gt; String
showList :: [Node k a] -&gt; ShowS
$cshowList :: forall k a. (Show a, Show k) =&gt; [Node k a] -&gt; ShowS
show :: Node k a -&gt; String
$cshow :: forall k a. (Show a, Show k) =&gt; Node k a -&gt; String
showsPrec :: Vertex -&gt; Node k a -&gt; ShowS
$cshowsPrec :: forall k a. (Show a, Show k) =&gt; Vertex -&gt; Node k a -&gt; ShowS
</span><a href="../../base/src/GHC.Show.html#Show"><span class="hs-identifier hs-var hs-var hs-var hs-var hs-var hs-var hs-var hs-var">Show</span></a></span></span></span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621679650690"><span id="local-6989586621679650696"><span class="annot"><span class="annottext">Node k a -&gt; Node k a -&gt; Bool
(Node k a -&gt; Node k a -&gt; Bool)
-&gt; (Node k a -&gt; Node k a -&gt; Bool) -&gt; Eq (Node k a)
forall a. (a -&gt; a -&gt; Bool) -&gt; (a -&gt; a -&gt; Bool) -&gt; Eq a
forall k a. (Eq a, Eq k) =&gt; Node k a -&gt; Node k a -&gt; Bool
/= :: Node k a -&gt; Node k a -&gt; Bool
$c/= :: forall k a. (Eq a, Eq k) =&gt; Node k a -&gt; Node k a -&gt; Bool
== :: Node k a -&gt; Node k a -&gt; Bool
$c== :: forall k a. (Eq a, Eq k) =&gt; Node k a -&gt; Node k a -&gt; Bool
</span><span class="hs-identifier hs-var hs-var hs-var hs-var hs-var hs-var">Eq</span></span></span></span><span class="hs-special">)</span><span>
</span><span id="line-190"></span><span>
</span><span id="line-191"></span><span class="hs-comment">-- | Get the value from a 'Node'.</span><span>
</span><span id="line-192"></span><span id="local-6989586621679651134"><span id="local-6989586621679651135"><span class="annot"><a href="Distribution.Compat.Graph.html#nodeValue"><span class="hs-identifier hs-type">nodeValue</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651135"><span class="hs-identifier hs-type">k</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651134"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679651134"><span class="hs-identifier hs-type">a</span></a></span></span></span><span>
</span><span id="line-193"></span><span id="nodeValue"><span class="annot"><span class="annottext">nodeValue :: forall k a. Node k a -&gt; a
</span><a href="Distribution.Compat.Graph.html#nodeValue"><span class="hs-identifier hs-var hs-var">nodeValue</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Compat.Graph.html#N"><span class="hs-identifier hs-type">N</span></a></span><span> </span><span id="local-6989586621679650689"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679650689"><span class="hs-identifier hs-var">a</span></a></span></span><span> </span><span class="annot"><span class="annottext">k
</span><span class="hs-identifier">_</span></span><span> </span><span class="annot"><span class="annottext">[k]
</span><span class="hs-identifier">_</span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679650689"><span class="hs-identifier hs-var">a</span></a></span><span>
</span><span id="line-194"></span><span>
</span><span id="line-195"></span><span id="local-6989586621679651129"><span class="hs-keyword">instance</span><span> </span><span id="local-6989586621679650686"><span class="annot"><a href="../../base/src/GHC.Base.html#Functor"><span class="hs-identifier hs-type">Functor</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Compat.Graph.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651129"><span class="hs-identifier hs-type">k</span></a></span><span class="hs-special">)</span></span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-196"></span><span>    </span><span id="local-6989586621679650684"><span class="annot"><span class="annottext">fmap :: forall a b. (a -&gt; b) -&gt; Node k a -&gt; Node k b
</span><a href="../../base/src/GHC.Base.html#fmap"><span class="hs-identifier hs-var hs-var hs-var hs-var">fmap</span></a></span></span><span> </span><span id="local-6989586621679650683"><span class="annot"><span class="annottext">a -&gt; b
</span><a href="#local-6989586621679650683"><span class="hs-identifier hs-var">f</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Compat.Graph.html#N"><span class="hs-identifier hs-type">N</span></a></span><span> </span><span id="local-6989586621679650682"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679650682"><span class="hs-identifier hs-var">a</span></a></span></span><span> </span><span id="local-6989586621679650681"><span class="annot"><span class="annottext">k
</span><a href="#local-6989586621679650681"><span class="hs-identifier hs-var">k</span></a></span></span><span> </span><span id="local-6989586621679650680"><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621679650680"><span class="hs-identifier hs-var">ks</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">b -&gt; k -&gt; [k] -&gt; Node k b
forall k a. a -&gt; k -&gt; [k] -&gt; Node k a
</span><a href="Distribution.Compat.Graph.html#N"><span class="hs-identifier hs-var">N</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a -&gt; b
</span><a href="#local-6989586621679650683"><span class="hs-identifier hs-var">f</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679650682"><span class="hs-identifier hs-var">a</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">k
</span><a href="#local-6989586621679650681"><span class="hs-identifier hs-var">k</span></a></span><span> </span><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621679650680"><span class="hs-identifier hs-var">ks</span></a></span></span><span>
</span><span id="line-197"></span><span>
</span><span id="line-198"></span><span id="local-6989586621679651123"><span id="local-6989586621679651124"><span class="hs-keyword">instance</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Ord</span></span><span> </span><span class="annot"><a href="#local-6989586621679651124"><span class="hs-identifier hs-type">k</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#IsNode"><span class="hs-identifier hs-type">IsNode</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Compat.Graph.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651124"><span class="hs-identifier hs-type">k</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651123"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-199"></span><span>    </span><span class="hs-keyword">type</span><span> </span><span id="Key"><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-var">Key</span></a></span></span><span> </span><span id="local-6989586621679651123"><span id="local-6989586621679651124"><span class="hs-special">(</span><span class="annot"><a href="Distribution.Compat.Graph.html#Node"><span class="hs-identifier hs-type">Node</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651124"><span class="hs-identifier hs-type">k</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651123"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><a href="#local-6989586621679651124"><span class="hs-identifier hs-type">k</span></a></span><span>
</span><span id="line-200"></span><span>    </span><span id="local-6989586621679650673"><span class="annot"><span class="annottext">nodeKey :: Node k a -&gt; Key (Node k a)
</span><a href="#local-6989586621679650673"><span class="hs-identifier hs-var hs-var hs-var hs-var">nodeKey</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Compat.Graph.html#N"><span class="hs-identifier hs-type">N</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><span class="hs-identifier">_</span></span><span> </span><span id="local-6989586621679650672"><span class="annot"><span class="annottext">k
</span><a href="#local-6989586621679650672"><span class="hs-identifier hs-var">k</span></a></span></span><span> </span><span class="annot"><span class="annottext">[k]
</span><span class="hs-identifier">_</span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">k
Key (Node k a)
</span><a href="#local-6989586621679650672"><span class="hs-identifier hs-var">k</span></a></span><span>
</span><span id="line-201"></span><span>    </span><span id="local-6989586621679650671"><span class="annot"><span class="annottext">nodeNeighbors :: Node k a -&gt; [Key (Node k a)]
</span><a href="#local-6989586621679650671"><span class="hs-identifier hs-var hs-var hs-var hs-var">nodeNeighbors</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Compat.Graph.html#N"><span class="hs-identifier hs-type">N</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><span class="hs-identifier">_</span></span><span> </span><span class="annot"><span class="annottext">k
</span><span class="hs-identifier">_</span></span><span> </span><span id="local-6989586621679650670"><span class="annot"><span class="annottext">[k]
</span><a href="#local-6989586621679650670"><span class="hs-identifier hs-var">ks</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[k]
[Key (Node k a)]
</span><a href="#local-6989586621679650670"><span class="hs-identifier hs-var">ks</span></a></span></span></span><span>
</span><span id="line-202"></span><span>
</span><span id="line-203"></span><span class="hs-comment">-- TODO: Maybe introduce a typeclass for items which just</span><span>
</span><span id="line-204"></span><span class="hs-comment">-- keys (so, Key associated type, and nodeKey method).  But</span><span>
</span><span id="line-205"></span><span class="hs-comment">-- I didn't need it here, so I didn't introduce it.</span><span>
</span><span id="line-206"></span><span>
</span><span id="line-207"></span><span class="hs-comment">-- Query</span><span>
</span><span id="line-208"></span><span>
</span><span id="line-209"></span><span class="hs-comment">-- | /O(1)/. Is the graph empty?</span><span>
</span><span id="line-210"></span><span id="local-6989586621679650669"><span class="annot"><a href="Distribution.Compat.Graph.html#null"><span class="hs-identifier hs-type">null</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679650669"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Bool</span></span></span><span>
</span><span id="line-211"></span><span id="null"><span class="annot"><span class="annottext">null :: forall a. Graph a -&gt; Bool
</span><a href="Distribution.Compat.Graph.html#null"><span class="hs-identifier hs-var hs-var">null</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Map (Key a) a -&gt; Bool
forall k a. Map k a -&gt; Bool
</span><a href="../../containers/src/Data.Map.Internal.html#null"><span class="hs-identifier hs-var">Map.null</span></a></span><span> </span><span class="annot"><span class="annottext">(Map (Key a) a -&gt; Bool)
-&gt; (Graph a -&gt; Map (Key a) a) -&gt; Graph a -&gt; Bool
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#toMap"><span class="hs-identifier hs-var">toMap</span></a></span><span>
</span><span id="line-212"></span><span>
</span><span id="line-213"></span><span class="hs-comment">-- | /O(1)/. The number of nodes in the graph.</span><span>
</span><span id="line-214"></span><span id="local-6989586621679650667"><span class="annot"><a href="Distribution.Compat.Graph.html#size"><span class="hs-identifier hs-type">size</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679650667"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Int</span></span></span><span>
</span><span id="line-215"></span><span id="size"><span class="annot"><span class="annottext">size :: forall a. Graph a -&gt; Vertex
</span><a href="Distribution.Compat.Graph.html#size"><span class="hs-identifier hs-var hs-var">size</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Map (Key a) a -&gt; Vertex
forall k a. Map k a -&gt; Vertex
</span><a href="../../containers/src/Data.Map.Internal.html#size"><span class="hs-identifier hs-var">Map.size</span></a></span><span> </span><span class="annot"><span class="annottext">(Map (Key a) a -&gt; Vertex)
-&gt; (Graph a -&gt; Map (Key a) a) -&gt; Graph a -&gt; Vertex
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#toMap"><span class="hs-identifier hs-var">toMap</span></a></span><span>
</span><span id="line-216"></span><span>
</span><span id="line-217"></span><span class="hs-comment">-- | /O(log V)/. Check if the key is in the graph.</span><span>
</span><span id="line-218"></span><span id="local-6989586621679651116"><span class="annot"><a href="Distribution.Compat.Graph.html#member"><span class="hs-identifier hs-type">member</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#IsNode"><span class="hs-identifier hs-type">IsNode</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651116"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651116"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651116"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="hs-identifier hs-type">Bool</span></span></span><span>
</span><span id="line-219"></span><span id="member"><span class="annot"><span class="annottext">member :: forall a. IsNode a =&gt; Key a -&gt; Graph a -&gt; Bool
</span><a href="Distribution.Compat.Graph.html#member"><span class="hs-identifier hs-var hs-var">member</span></a></span></span><span> </span><span id="local-6989586621679650661"><span class="annot"><span class="annottext">Key a
</span><a href="#local-6989586621679650661"><span class="hs-identifier hs-var">k</span></a></span></span><span> </span><span id="local-6989586621679650660"><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650660"><span class="hs-identifier hs-var">g</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Key a -&gt; Map (Key a) a -&gt; Bool
forall k a. Ord k =&gt; k -&gt; Map k a -&gt; Bool
</span><a href="../../containers/src/Data.Map.Internal.html#member"><span class="hs-identifier hs-var">Map.member</span></a></span><span> </span><span class="annot"><span class="annottext">Key a
</span><a href="#local-6989586621679650661"><span class="hs-identifier hs-var">k</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#toMap"><span class="hs-identifier hs-var">toMap</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650660"><span class="hs-identifier hs-var">g</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-220"></span><span>
</span><span id="line-221"></span><span class="hs-comment">-- | /O(log V)/. Lookup the node at a key in the graph.</span><span>
</span><span id="line-222"></span><span id="local-6989586621679651112"><span class="annot"><a href="Distribution.Compat.Graph.html#lookup"><span class="hs-identifier hs-type">lookup</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#IsNode"><span class="hs-identifier hs-type">IsNode</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651112"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651112"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651112"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Maybe"><span class="hs-identifier hs-type">Maybe</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651112"><span class="hs-identifier hs-type">a</span></a></span></span><span>
</span><span id="line-223"></span><span id="lookup"><span class="annot"><span class="annottext">lookup :: forall a. IsNode a =&gt; Key a -&gt; Graph a -&gt; Maybe a
</span><a href="Distribution.Compat.Graph.html#lookup"><span class="hs-identifier hs-var hs-var">lookup</span></a></span></span><span> </span><span id="local-6989586621679650654"><span class="annot"><span class="annottext">Key a
</span><a href="#local-6989586621679650654"><span class="hs-identifier hs-var">k</span></a></span></span><span> </span><span id="local-6989586621679650653"><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650653"><span class="hs-identifier hs-var">g</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Key a -&gt; Map (Key a) a -&gt; Maybe a
forall k a. Ord k =&gt; k -&gt; Map k a -&gt; Maybe a
</span><a href="../../containers/src/Data.Map.Internal.html#lookup"><span class="hs-identifier hs-var">Map.lookup</span></a></span><span> </span><span class="annot"><span class="annottext">Key a
</span><a href="#local-6989586621679650654"><span class="hs-identifier hs-var">k</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#toMap"><span class="hs-identifier hs-var">toMap</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650653"><span class="hs-identifier hs-var">g</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-224"></span><span>
</span><span id="line-225"></span><span class="hs-comment">-- Construction</span><span>
</span><span id="line-226"></span><span>
</span><span id="line-227"></span><span class="hs-comment">-- | /O(1)/. The empty graph.</span><span>
</span><span id="line-228"></span><span id="local-6989586621679651108"><span class="annot"><a href="Distribution.Compat.Graph.html#empty"><span class="hs-identifier hs-type">empty</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#IsNode"><span class="hs-identifier hs-type">IsNode</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651108"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651108"><span class="hs-identifier hs-type">a</span></a></span></span><span>
</span><span id="line-229"></span><span id="empty"><span class="annot"><span class="annottext">empty :: forall a. IsNode a =&gt; Graph a
</span><a href="Distribution.Compat.Graph.html#empty"><span class="hs-identifier hs-var hs-var">empty</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Map (Key a) a -&gt; Graph a
forall a. IsNode a =&gt; Map (Key a) a -&gt; Graph a
</span><a href="Distribution.Compat.Graph.html#fromMap"><span class="hs-identifier hs-var">fromMap</span></a></span><span> </span><span class="annot"><span class="annottext">Map (Key a) a
forall k a. Map k a
</span><a href="../../containers/src/Data.Map.Internal.html#empty"><span class="hs-identifier hs-var">Map.empty</span></a></span><span>
</span><span id="line-230"></span><span>
</span><span id="line-231"></span><span class="hs-comment">-- | /O(log V)/. Insert a node into a graph.</span><span>
</span><span id="line-232"></span><span id="local-6989586621679651103"><span class="annot"><a href="Distribution.Compat.Graph.html#insert"><span class="hs-identifier hs-type">insert</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#IsNode"><span class="hs-identifier hs-type">IsNode</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651103"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679651103"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651103"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651103"><span class="hs-identifier hs-type">a</span></a></span></span><span>
</span><span id="line-233"></span><span id="insert"><span class="annot"><span class="annottext">insert :: forall a. IsNode a =&gt; a -&gt; Graph a -&gt; Graph a
</span><a href="Distribution.Compat.Graph.html#insert"><span class="hs-identifier hs-var hs-var">insert</span></a></span></span><span> </span><span class="hs-glyph">!</span><span id="local-6989586621679650640"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679650640"><span class="hs-identifier hs-var">n</span></a></span></span><span> </span><span id="local-6989586621679650639"><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650639"><span class="hs-identifier hs-var">g</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Map (Key a) a -&gt; Graph a
forall a. IsNode a =&gt; Map (Key a) a -&gt; Graph a
</span><a href="Distribution.Compat.Graph.html#fromMap"><span class="hs-identifier hs-var">fromMap</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Key a -&gt; a -&gt; Map (Key a) a -&gt; Map (Key a) a
forall k a. Ord k =&gt; k -&gt; a -&gt; Map k a -&gt; Map k a
</span><a href="../../containers/src/Data.Map.Strict.Internal.html#insert"><span class="hs-identifier hs-var">Map.insert</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a -&gt; Key a
forall a. IsNode a =&gt; a -&gt; Key a
</span><a href="Distribution.Compat.Graph.html#nodeKey"><span class="hs-identifier hs-var">nodeKey</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679650640"><span class="hs-identifier hs-var">n</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679650640"><span class="hs-identifier hs-var">n</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#toMap"><span class="hs-identifier hs-var">toMap</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650639"><span class="hs-identifier hs-var">g</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-234"></span><span>
</span><span id="line-235"></span><span class="hs-comment">-- | /O(log V)/. Delete the node at a key from the graph.</span><span>
</span><span id="line-236"></span><span id="local-6989586621679651099"><span class="annot"><a href="Distribution.Compat.Graph.html#deleteKey"><span class="hs-identifier hs-type">deleteKey</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#IsNode"><span class="hs-identifier hs-type">IsNode</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651099"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651099"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651099"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651099"><span class="hs-identifier hs-type">a</span></a></span></span><span>
</span><span id="line-237"></span><span id="deleteKey"><span class="annot"><span class="annottext">deleteKey :: forall a. IsNode a =&gt; Key a -&gt; Graph a -&gt; Graph a
</span><a href="Distribution.Compat.Graph.html#deleteKey"><span class="hs-identifier hs-var hs-var">deleteKey</span></a></span></span><span> </span><span id="local-6989586621679650632"><span class="annot"><span class="annottext">Key a
</span><a href="#local-6989586621679650632"><span class="hs-identifier hs-var">k</span></a></span></span><span> </span><span id="local-6989586621679650631"><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650631"><span class="hs-identifier hs-var">g</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Map (Key a) a -&gt; Graph a
forall a. IsNode a =&gt; Map (Key a) a -&gt; Graph a
</span><a href="Distribution.Compat.Graph.html#fromMap"><span class="hs-identifier hs-var">fromMap</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Key a -&gt; Map (Key a) a -&gt; Map (Key a) a
forall k a. Ord k =&gt; k -&gt; Map k a -&gt; Map k a
</span><a href="../../containers/src/Data.Map.Internal.html#delete"><span class="hs-identifier hs-var">Map.delete</span></a></span><span> </span><span class="annot"><span class="annottext">Key a
</span><a href="#local-6989586621679650632"><span class="hs-identifier hs-var">k</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#toMap"><span class="hs-identifier hs-var">toMap</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650631"><span class="hs-identifier hs-var">g</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-238"></span><span>
</span><span id="line-239"></span><span class="hs-comment">-- | /O(log V)/. Lookup and delete.  This function returns the deleted</span><span>
</span><span id="line-240"></span><span class="hs-comment">-- value if it existed.</span><span>
</span><span id="line-241"></span><span id="local-6989586621679651095"><span class="annot"><a href="Distribution.Compat.Graph.html#deleteLookup"><span class="hs-identifier hs-type">deleteLookup</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#IsNode"><span class="hs-identifier hs-type">IsNode</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651095"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651095"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651095"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Maybe"><span class="hs-identifier hs-type">Maybe</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651095"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651095"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span></span><span>
</span><span id="line-242"></span><span id="deleteLookup"><span class="annot"><span class="annottext">deleteLookup :: forall a. IsNode a =&gt; Key a -&gt; Graph a -&gt; (Maybe a, Graph a)
</span><a href="Distribution.Compat.Graph.html#deleteLookup"><span class="hs-identifier hs-var hs-var">deleteLookup</span></a></span></span><span> </span><span id="local-6989586621679650624"><span class="annot"><span class="annottext">Key a
</span><a href="#local-6989586621679650624"><span class="hs-identifier hs-var">k</span></a></span></span><span> </span><span id="local-6989586621679650623"><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650623"><span class="hs-identifier hs-var">g</span></a></span></span><span> </span><span class="hs-glyph">=</span><span>
</span><span id="line-243"></span><span>    </span><span class="hs-keyword">let</span><span> </span><span class="hs-special">(</span><span id="local-6989586621679650622"><span class="annot"><span class="annottext">Maybe a
</span><a href="#local-6989586621679650622"><span class="hs-identifier hs-var">r</span></a></span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621679650621"><span class="annot"><span class="annottext">Map (Key a) a
</span><a href="#local-6989586621679650621"><span class="hs-identifier hs-var">m'</span></a></span></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(Key a -&gt; a -&gt; Maybe a)
-&gt; Key a -&gt; Map (Key a) a -&gt; (Maybe a, Map (Key a) a)
forall k a.
Ord k =&gt;
(k -&gt; a -&gt; Maybe a) -&gt; k -&gt; Map k a -&gt; (Maybe a, Map k a)
</span><a href="../../containers/src/Data.Map.Strict.Internal.html#updateLookupWithKey"><span class="hs-identifier hs-var">Map.updateLookupWithKey</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-glyph">\</span><span class="annot"><span class="annottext">Key a
</span><span class="hs-identifier">_</span></span><span> </span><span class="annot"><span class="annottext">a
</span><span class="hs-identifier">_</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">Maybe a
forall a. Maybe a
</span><a href="../../base/src/GHC.Maybe.html#Nothing"><span class="hs-identifier hs-var">Nothing</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">Key a
</span><a href="#local-6989586621679650624"><span class="hs-identifier hs-var">k</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#toMap"><span class="hs-identifier hs-var">toMap</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650623"><span class="hs-identifier hs-var">g</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-244"></span><span>    </span><span class="hs-keyword">in</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Maybe a
</span><a href="#local-6989586621679650622"><span class="hs-identifier hs-var">r</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">Map (Key a) a -&gt; Graph a
forall a. IsNode a =&gt; Map (Key a) a -&gt; Graph a
</span><a href="Distribution.Compat.Graph.html#fromMap"><span class="hs-identifier hs-var">fromMap</span></a></span><span> </span><span class="annot"><span class="annottext">Map (Key a) a
</span><a href="#local-6989586621679650621"><span class="hs-identifier hs-var">m'</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-245"></span><span>
</span><span id="line-246"></span><span class="hs-comment">-- Combining</span><span>
</span><span id="line-247"></span><span>
</span><span id="line-248"></span><span class="hs-comment">-- | /O(V + V')/. Right-biased union, preferring entries</span><span>
</span><span id="line-249"></span><span class="hs-comment">-- from the second map when conflicts occur.</span><span>
</span><span id="line-250"></span><span class="hs-comment">-- @'nodeKey' x = 'nodeKey' (f x)@.</span><span>
</span><span id="line-251"></span><span id="local-6989586621679651091"><span class="annot"><a href="Distribution.Compat.Graph.html#unionRight"><span class="hs-identifier hs-type">unionRight</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#IsNode"><span class="hs-identifier hs-type">IsNode</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651091"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651091"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651091"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651091"><span class="hs-identifier hs-type">a</span></a></span></span><span>
</span><span id="line-252"></span><span id="unionRight"><span class="annot"><span class="annottext">unionRight :: forall a. IsNode a =&gt; Graph a -&gt; Graph a -&gt; Graph a
</span><a href="Distribution.Compat.Graph.html#unionRight"><span class="hs-identifier hs-var hs-var">unionRight</span></a></span></span><span> </span><span id="local-6989586621679650614"><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650614"><span class="hs-identifier hs-var">g</span></a></span></span><span> </span><span id="local-6989586621679650613"><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650613"><span class="hs-identifier hs-var">g'</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Map (Key a) a -&gt; Graph a
forall a. IsNode a =&gt; Map (Key a) a -&gt; Graph a
</span><a href="Distribution.Compat.Graph.html#fromMap"><span class="hs-identifier hs-var">fromMap</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Map (Key a) a -&gt; Map (Key a) a -&gt; Map (Key a) a
forall k a. Ord k =&gt; Map k a -&gt; Map k a -&gt; Map k a
</span><a href="../../containers/src/Data.Map.Internal.html#union"><span class="hs-identifier hs-var">Map.union</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#toMap"><span class="hs-identifier hs-var">toMap</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650613"><span class="hs-identifier hs-var">g'</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#toMap"><span class="hs-identifier hs-var">toMap</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650614"><span class="hs-identifier hs-var">g</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-253"></span><span>
</span><span id="line-254"></span><span class="hs-comment">-- | /O(V + V')/. Left-biased union, preferring entries from</span><span>
</span><span id="line-255"></span><span class="hs-comment">-- the first map when conflicts occur.</span><span>
</span><span id="line-256"></span><span id="local-6989586621679650611"><span class="annot"><a href="Distribution.Compat.Graph.html#unionLeft"><span class="hs-identifier hs-type">unionLeft</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#IsNode"><span class="hs-identifier hs-type">IsNode</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679650611"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679650611"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679650611"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679650611"><span class="hs-identifier hs-type">a</span></a></span></span><span>
</span><span id="line-257"></span><span id="unionLeft"><span class="annot"><span class="annottext">unionLeft :: forall a. IsNode a =&gt; Graph a -&gt; Graph a -&gt; Graph a
</span><a href="Distribution.Compat.Graph.html#unionLeft"><span class="hs-identifier hs-var hs-var">unionLeft</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(Graph a -&gt; Graph a -&gt; Graph a) -&gt; Graph a -&gt; Graph a -&gt; Graph a
forall a b c. (a -&gt; b -&gt; c) -&gt; b -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#flip"><span class="hs-identifier hs-var">flip</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a -&gt; Graph a -&gt; Graph a
forall a. IsNode a =&gt; Graph a -&gt; Graph a -&gt; Graph a
</span><a href="Distribution.Compat.Graph.html#unionRight"><span class="hs-identifier hs-var">unionRight</span></a></span><span>
</span><span id="line-258"></span><span>
</span><span id="line-259"></span><span class="hs-comment">-- Graph-like operations</span><span>
</span><span id="line-260"></span><span>
</span><span id="line-261"></span><span class="hs-comment">-- | /&#937;(V + E)/. Compute the strongly connected components of a graph.</span><span>
</span><span id="line-262"></span><span class="hs-comment">-- Requires amortized construction of graph.</span><span>
</span><span id="line-263"></span><span id="local-6989586621679651083"><span class="annot"><a href="Distribution.Compat.Graph.html#stronglyConnComp"><span class="hs-identifier hs-type">stronglyConnComp</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651083"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="../../containers/src/Data.Graph.html#SCC"><span class="hs-identifier hs-type">SCC</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651083"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span></span><span>
</span><span id="line-264"></span><span id="stronglyConnComp"><span class="annot"><span class="annottext">stronglyConnComp :: forall a. Graph a -&gt; [SCC a]
</span><a href="Distribution.Compat.Graph.html#stronglyConnComp"><span class="hs-identifier hs-var hs-var">stronglyConnComp</span></a></span></span><span> </span><span id="local-6989586621679650600"><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650600"><span class="hs-identifier hs-var">g</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(Tree Vertex -&gt; SCC a) -&gt; [Tree Vertex] -&gt; [SCC a]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="annot"><span class="annottext">Tree Vertex -&gt; SCC a
</span><a href="#local-6989586621679650599"><span class="hs-identifier hs-var">decode</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree Vertex]
</span><a href="#local-6989586621679650598"><span class="hs-identifier hs-var">forest</span></a></span><span>
</span><span id="line-265"></span><span>  </span><span class="hs-keyword">where</span><span>
</span><span id="line-266"></span><span>    </span><span id="local-6989586621679650598"><span class="annot"><span class="annottext">forest :: [Tree Vertex]
</span><a href="#local-6989586621679650598"><span class="hs-identifier hs-var hs-var">forest</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Graph -&gt; [Tree Vertex]
</span><a href="../../containers/src/Data.Graph.html#scc"><span class="hs-identifier hs-var">G.scc</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; Graph
forall a. Graph a -&gt; Graph
</span><a href="Distribution.Compat.Graph.html#graphForward"><span class="hs-identifier hs-var hs-var">graphForward</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650600"><span class="hs-identifier hs-var">g</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-267"></span><span>    </span><span id="local-6989586621679650599"><span class="annot"><span class="annottext">decode :: Tree Vertex -&gt; SCC a
</span><a href="#local-6989586621679650599"><span class="hs-identifier hs-var hs-var">decode</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../containers/src/Data.Tree.html#Node"><span class="hs-identifier hs-type">Tree.Node</span></a></span><span> </span><span id="local-6989586621679650595"><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621679650595"><span class="hs-identifier hs-var">v</span></a></span></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span class="hs-special">)</span><span>
</span><span id="line-268"></span><span>        </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Vertex -&gt; Bool
</span><a href="#local-6989586621679650594"><span class="hs-identifier hs-var">mentions_itself</span></a></span><span> </span><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621679650595"><span class="hs-identifier hs-var">v</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[a] -&gt; SCC a
forall vertex. [vertex] -&gt; SCC vertex
</span><a href="../../containers/src/Data.Graph.html#CyclicSCC"><span class="hs-identifier hs-var">CyclicSCC</span></a></span><span>  </span><span class="hs-special">[</span><span class="annot"><span class="annottext">Graph a -&gt; Vertex -&gt; a
forall a. Graph a -&gt; Vertex -&gt; a
</span><a href="Distribution.Compat.Graph.html#graphVertexToNode"><span class="hs-identifier hs-var hs-var">graphVertexToNode</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650600"><span class="hs-identifier hs-var">g</span></a></span><span> </span><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621679650595"><span class="hs-identifier hs-var">v</span></a></span><span class="hs-special">]</span><span>
</span><span id="line-269"></span><span>        </span><span class="hs-glyph">|</span><span> </span><span class="annot"><span class="annottext">Bool
</span><a href="../../base/src/GHC.Base.html#otherwise"><span class="hs-identifier hs-var">otherwise</span></a></span><span>         </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">a -&gt; SCC a
forall vertex. vertex -&gt; SCC vertex
</span><a href="../../containers/src/Data.Graph.html#AcyclicSCC"><span class="hs-identifier hs-var">AcyclicSCC</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; Vertex -&gt; a
forall a. Graph a -&gt; Vertex -&gt; a
</span><a href="Distribution.Compat.Graph.html#graphVertexToNode"><span class="hs-identifier hs-var hs-var">graphVertexToNode</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650600"><span class="hs-identifier hs-var">g</span></a></span><span> </span><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621679650595"><span class="hs-identifier hs-var">v</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-270"></span><span>    </span><span class="annot"><a href="#local-6989586621679650599"><span class="hs-identifier hs-var">decode</span></a></span><span> </span><span id="local-6989586621679650591"><span class="annot"><span class="annottext">Tree Vertex
</span><a href="#local-6989586621679650591"><span class="hs-identifier hs-var">other</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[a] -&gt; SCC a
forall vertex. [vertex] -&gt; SCC vertex
</span><a href="../../containers/src/Data.Graph.html#CyclicSCC"><span class="hs-identifier hs-var">CyclicSCC</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Tree Vertex -&gt; [a] -&gt; [a]
</span><a href="#local-6989586621679650590"><span class="hs-identifier hs-var">dec</span></a></span><span> </span><span class="annot"><span class="annottext">Tree Vertex
</span><a href="#local-6989586621679650591"><span class="hs-identifier hs-var">other</span></a></span><span> </span><span class="hs-special">[</span><span class="hs-special">]</span><span class="hs-special">)</span><span>
</span><span id="line-271"></span><span>        </span><span class="hs-keyword">where</span><span> </span><span id="local-6989586621679650590"><span class="annot"><span class="annottext">dec :: Tree Vertex -&gt; [a] -&gt; [a]
</span><a href="#local-6989586621679650590"><span class="hs-identifier hs-var hs-var">dec</span></a></span></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../containers/src/Data.Tree.html#Node"><span class="hs-identifier hs-type">Tree.Node</span></a></span><span> </span><span id="local-6989586621679650589"><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621679650589"><span class="hs-identifier hs-var">v</span></a></span></span><span> </span><span id="local-6989586621679650588"><span class="annot"><span class="annottext">[Tree Vertex]
</span><a href="#local-6989586621679650588"><span class="hs-identifier hs-var">ts</span></a></span></span><span class="hs-special">)</span><span> </span><span id="local-6989586621679650587"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621679650587"><span class="hs-identifier hs-var">vs</span></a></span></span><span>
</span><span id="line-272"></span><span>                </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Graph a -&gt; Vertex -&gt; a
forall a. Graph a -&gt; Vertex -&gt; a
</span><a href="Distribution.Compat.Graph.html#graphVertexToNode"><span class="hs-identifier hs-var hs-var">graphVertexToNode</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650600"><span class="hs-identifier hs-var">g</span></a></span><span> </span><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621679650589"><span class="hs-identifier hs-var">v</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; [a] -&gt; [a]
forall a. a -&gt; [a] -&gt; [a]
</span><span class="hs-glyph hs-var">:</span></span><span> </span><span class="annot"><span class="annottext">(Tree Vertex -&gt; [a] -&gt; [a]) -&gt; [a] -&gt; [Tree Vertex] -&gt; [a]
forall (t :: * -&gt; *) a b.
Foldable t =&gt;
(a -&gt; b -&gt; b) -&gt; b -&gt; t a -&gt; b
</span><a href="../../base/src/Data.Foldable.html#foldr"><span class="hs-identifier hs-var">foldr</span></a></span><span> </span><span class="annot"><span class="annottext">Tree Vertex -&gt; [a] -&gt; [a]
</span><a href="#local-6989586621679650590"><span class="hs-identifier hs-var">dec</span></a></span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621679650587"><span class="hs-identifier hs-var">vs</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree Vertex]
</span><a href="#local-6989586621679650588"><span class="hs-identifier hs-var">ts</span></a></span><span>
</span><span id="line-273"></span><span>    </span><span id="local-6989586621679650594"><span class="annot"><span class="annottext">mentions_itself :: Vertex -&gt; Bool
</span><a href="#local-6989586621679650594"><span class="hs-identifier hs-var hs-var">mentions_itself</span></a></span></span><span> </span><span id="local-6989586621679650586"><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621679650586"><span class="hs-identifier hs-var">v</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621679650586"><span class="hs-identifier hs-var">v</span></a></span><span> </span><span class="annot"><span class="annottext">Vertex -&gt; [Vertex] -&gt; Bool
forall (t :: * -&gt; *) a. (Foldable t, Eq a) =&gt; a -&gt; t a -&gt; Bool
</span><a href="../../base/src/Data.Foldable.html#elem"><span class="hs-operator hs-var">`elem`</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; Graph
forall a. Graph a -&gt; Graph
</span><a href="Distribution.Compat.Graph.html#graphForward"><span class="hs-identifier hs-var hs-var">graphForward</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650600"><span class="hs-identifier hs-var">g</span></a></span><span> </span><span class="annot"><span class="annottext">Graph -&gt; Vertex -&gt; [Vertex]
forall i e. Ix i =&gt; Array i e -&gt; i -&gt; e
</span><a href="../../base/src/GHC.Arr.html#%21"><span class="hs-operator hs-var">!</span></a></span><span> </span><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621679650586"><span class="hs-identifier hs-var">v</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-274"></span><span class="hs-comment">-- Implementation copied from 'stronglyConnCompR' in 'Data.Graph'.</span><span>
</span><span id="line-275"></span><span>
</span><span id="line-276"></span><span class="hs-comment">-- | /&#937;(V + E)/. Compute the cycles of a graph.</span><span>
</span><span id="line-277"></span><span class="hs-comment">-- Requires amortized construction of graph.</span><span>
</span><span id="line-278"></span><span id="local-6989586621679651075"><span class="annot"><a href="Distribution.Compat.Graph.html#cycles"><span class="hs-identifier hs-type">cycles</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651075"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679651075"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span class="hs-special">]</span></span><span>
</span><span id="line-279"></span><span id="cycles"><span class="annot"><span class="annottext">cycles :: forall a. Graph a -&gt; [[a]]
</span><a href="Distribution.Compat.Graph.html#cycles"><span class="hs-identifier hs-var hs-var">cycles</span></a></span></span><span> </span><span id="local-6989586621679650585"><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650585"><span class="hs-identifier hs-var">g</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">[</span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621679650584"><span class="hs-identifier hs-var">vs</span></a></span><span> </span><span class="hs-glyph">|</span><span> </span><span class="annot"><a href="../../containers/src/Data.Graph.html#CyclicSCC"><span class="hs-identifier hs-type">CyclicSCC</span></a></span><span> </span><span id="local-6989586621679650584"><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621679650584"><span class="hs-identifier hs-var">vs</span></a></span></span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">Graph a -&gt; [SCC a]
forall a. Graph a -&gt; [SCC a]
</span><a href="Distribution.Compat.Graph.html#stronglyConnComp"><span class="hs-identifier hs-var">stronglyConnComp</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650585"><span class="hs-identifier hs-var">g</span></a></span><span> </span><span class="hs-special">]</span><span>
</span><span id="line-280"></span><span>
</span><span id="line-281"></span><span class="hs-comment">-- | /O(1)/.  Return a list of nodes paired with their broken</span><span>
</span><span id="line-282"></span><span class="hs-comment">-- neighbors (i.e., neighbor keys which are not in the graph).</span><span>
</span><span id="line-283"></span><span class="hs-comment">-- Requires amortized construction of graph.</span><span>
</span><span id="line-284"></span><span id="local-6989586621679650583"><span class="annot"><a href="Distribution.Compat.Graph.html#broken"><span class="hs-identifier hs-type">broken</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679650583"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679650583"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">,</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679650583"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span class="hs-special">)</span><span class="hs-special">]</span></span><span>
</span><span id="line-285"></span><span id="broken"><span class="annot"><span class="annottext">broken :: forall a. Graph a -&gt; [(a, [Key a])]
</span><a href="Distribution.Compat.Graph.html#broken"><span class="hs-identifier hs-var hs-var">broken</span></a></span></span><span> </span><span id="local-6989586621679650582"><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650582"><span class="hs-identifier hs-var">g</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Graph a -&gt; [(a, [Key a])]
forall a. Graph a -&gt; [(a, [Key a])]
</span><a href="Distribution.Compat.Graph.html#graphBroken"><span class="hs-identifier hs-var hs-var">graphBroken</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650582"><span class="hs-identifier hs-var">g</span></a></span><span>
</span><span id="line-286"></span><span>
</span><span id="line-287"></span><span class="hs-comment">-- | Lookup the immediate neighbors from a key in the graph.</span><span>
</span><span id="line-288"></span><span class="hs-comment">-- Requires amortized construction of graph.</span><span>
</span><span id="line-289"></span><span id="local-6989586621679651072"><span class="annot"><a href="Distribution.Compat.Graph.html#neighbors"><span class="hs-identifier hs-type">neighbors</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651072"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651072"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Maybe"><span class="hs-identifier hs-type">Maybe</span></a></span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679651072"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span></span><span>
</span><span id="line-290"></span><span id="neighbors"><span class="annot"><span class="annottext">neighbors :: forall a. Graph a -&gt; Key a -&gt; Maybe [a]
</span><a href="Distribution.Compat.Graph.html#neighbors"><span class="hs-identifier hs-var hs-var">neighbors</span></a></span></span><span> </span><span id="local-6989586621679650577"><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650577"><span class="hs-identifier hs-var">g</span></a></span></span><span> </span><span id="local-6989586621679650576"><span class="annot"><span class="annottext">Key a
</span><a href="#local-6989586621679650576"><span class="hs-identifier hs-var">k</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-keyword">do</span><span>
</span><span id="line-291"></span><span>    </span><span id="local-6989586621679650575"><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621679650575"><span class="hs-identifier hs-var">v</span></a></span></span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">Graph a -&gt; Key a -&gt; Maybe Vertex
forall a. Graph a -&gt; Key a -&gt; Maybe Vertex
</span><a href="Distribution.Compat.Graph.html#graphKeyToVertex"><span class="hs-identifier hs-var hs-var">graphKeyToVertex</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650577"><span class="hs-identifier hs-var">g</span></a></span><span> </span><span class="annot"><span class="annottext">Key a
</span><a href="#local-6989586621679650576"><span class="hs-identifier hs-var">k</span></a></span><span>
</span><span id="line-292"></span><span>    </span><span class="annot"><span class="annottext">[a] -&gt; Maybe [a]
forall (m :: * -&gt; *) a. Monad m =&gt; a -&gt; m a
</span><a href="../../base/src/GHC.Base.html#return"><span class="hs-identifier hs-var">return</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(Vertex -&gt; a) -&gt; [Vertex] -&gt; [a]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; Vertex -&gt; a
forall a. Graph a -&gt; Vertex -&gt; a
</span><a href="Distribution.Compat.Graph.html#graphVertexToNode"><span class="hs-identifier hs-var hs-var">graphVertexToNode</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650577"><span class="hs-identifier hs-var">g</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; Graph
forall a. Graph a -&gt; Graph
</span><a href="Distribution.Compat.Graph.html#graphForward"><span class="hs-identifier hs-var hs-var">graphForward</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650577"><span class="hs-identifier hs-var">g</span></a></span><span> </span><span class="annot"><span class="annottext">Graph -&gt; Vertex -&gt; [Vertex]
forall i e. Ix i =&gt; Array i e -&gt; i -&gt; e
</span><a href="../../base/src/GHC.Arr.html#%21"><span class="hs-operator hs-var">!</span></a></span><span> </span><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621679650575"><span class="hs-identifier hs-var">v</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-293"></span><span>
</span><span id="line-294"></span><span class="hs-comment">-- | Lookup the immediate reverse neighbors from a key in the graph.</span><span>
</span><span id="line-295"></span><span class="hs-comment">-- Requires amortized construction of graph.</span><span>
</span><span id="line-296"></span><span id="local-6989586621679650574"><span class="annot"><a href="Distribution.Compat.Graph.html#revNeighbors"><span class="hs-identifier hs-type">revNeighbors</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679650574"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679650574"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Maybe"><span class="hs-identifier hs-type">Maybe</span></a></span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679650574"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span></span><span>
</span><span id="line-297"></span><span id="revNeighbors"><span class="annot"><span class="annottext">revNeighbors :: forall a. Graph a -&gt; Key a -&gt; Maybe [a]
</span><a href="Distribution.Compat.Graph.html#revNeighbors"><span class="hs-identifier hs-var hs-var">revNeighbors</span></a></span></span><span> </span><span id="local-6989586621679650570"><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650570"><span class="hs-identifier hs-var">g</span></a></span></span><span> </span><span id="local-6989586621679650569"><span class="annot"><span class="annottext">Key a
</span><a href="#local-6989586621679650569"><span class="hs-identifier hs-var">k</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-keyword">do</span><span>
</span><span id="line-298"></span><span>    </span><span id="local-6989586621679650568"><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621679650568"><span class="hs-identifier hs-var">v</span></a></span></span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">Graph a -&gt; Key a -&gt; Maybe Vertex
forall a. Graph a -&gt; Key a -&gt; Maybe Vertex
</span><a href="Distribution.Compat.Graph.html#graphKeyToVertex"><span class="hs-identifier hs-var hs-var">graphKeyToVertex</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650570"><span class="hs-identifier hs-var">g</span></a></span><span> </span><span class="annot"><span class="annottext">Key a
</span><a href="#local-6989586621679650569"><span class="hs-identifier hs-var">k</span></a></span><span>
</span><span id="line-299"></span><span>    </span><span class="annot"><span class="annottext">[a] -&gt; Maybe [a]
forall (m :: * -&gt; *) a. Monad m =&gt; a -&gt; m a
</span><a href="../../base/src/GHC.Base.html#return"><span class="hs-identifier hs-var">return</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(Vertex -&gt; a) -&gt; [Vertex] -&gt; [a]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; Vertex -&gt; a
forall a. Graph a -&gt; Vertex -&gt; a
</span><a href="Distribution.Compat.Graph.html#graphVertexToNode"><span class="hs-identifier hs-var hs-var">graphVertexToNode</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650570"><span class="hs-identifier hs-var">g</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; Graph
forall a. Graph a -&gt; Graph
</span><a href="Distribution.Compat.Graph.html#graphAdjoint"><span class="hs-identifier hs-var hs-var">graphAdjoint</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650570"><span class="hs-identifier hs-var">g</span></a></span><span> </span><span class="annot"><span class="annottext">Graph -&gt; Vertex -&gt; [Vertex]
forall i e. Ix i =&gt; Array i e -&gt; i -&gt; e
</span><a href="../../base/src/GHC.Arr.html#%21"><span class="hs-operator hs-var">!</span></a></span><span> </span><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621679650568"><span class="hs-identifier hs-var">v</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-300"></span><span>
</span><span id="line-301"></span><span class="hs-comment">-- | Compute the subgraph which is the closure of some set of keys.</span><span>
</span><span id="line-302"></span><span class="hs-comment">-- Returns @Nothing@ if one (or more) keys are not present in</span><span>
</span><span id="line-303"></span><span class="hs-comment">-- the graph.</span><span>
</span><span id="line-304"></span><span class="hs-comment">-- Requires amortized construction of graph.</span><span>
</span><span id="line-305"></span><span id="local-6989586621679651067"><span class="annot"><a href="Distribution.Compat.Graph.html#closure"><span class="hs-identifier hs-type">closure</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651067"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651067"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Maybe"><span class="hs-identifier hs-type">Maybe</span></a></span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679651067"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span></span><span>
</span><span id="line-306"></span><span id="closure"><span class="annot"><span class="annottext">closure :: forall a. Graph a -&gt; [Key a] -&gt; Maybe [a]
</span><a href="Distribution.Compat.Graph.html#closure"><span class="hs-identifier hs-var hs-var">closure</span></a></span></span><span> </span><span id="local-6989586621679650561"><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650561"><span class="hs-identifier hs-var">g</span></a></span></span><span> </span><span id="local-6989586621679650560"><span class="annot"><span class="annottext">[Key a]
</span><a href="#local-6989586621679650560"><span class="hs-identifier hs-var">ks</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-keyword">do</span><span>
</span><span id="line-307"></span><span>    </span><span id="local-6989586621679650559"><span class="annot"><span class="annottext">[Vertex]
</span><a href="#local-6989586621679650559"><span class="hs-identifier hs-var">vs</span></a></span></span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">(Key a -&gt; Maybe Vertex) -&gt; [Key a] -&gt; Maybe [Vertex]
forall (t :: * -&gt; *) (f :: * -&gt; *) a b.
(Traversable t, Applicative f) =&gt;
(a -&gt; f b) -&gt; t a -&gt; f (t b)
</span><a href="../../base/src/Data.Traversable.html#traverse"><span class="hs-identifier hs-var">traverse</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; Key a -&gt; Maybe Vertex
forall a. Graph a -&gt; Key a -&gt; Maybe Vertex
</span><a href="Distribution.Compat.Graph.html#graphKeyToVertex"><span class="hs-identifier hs-var hs-var">graphKeyToVertex</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650561"><span class="hs-identifier hs-var">g</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[Key a]
</span><a href="#local-6989586621679650560"><span class="hs-identifier hs-var">ks</span></a></span><span>
</span><span id="line-308"></span><span>    </span><span class="annot"><span class="annottext">[a] -&gt; Maybe [a]
forall (m :: * -&gt; *) a. Monad m =&gt; a -&gt; m a
</span><a href="../../base/src/GHC.Base.html#return"><span class="hs-identifier hs-var">return</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; [Tree Vertex] -&gt; [a]
forall a. Graph a -&gt; [Tree Vertex] -&gt; [a]
</span><a href="Distribution.Compat.Graph.html#decodeVertexForest"><span class="hs-identifier hs-var">decodeVertexForest</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650561"><span class="hs-identifier hs-var">g</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph -&gt; [Vertex] -&gt; [Tree Vertex]
</span><a href="../../containers/src/Data.Graph.html#dfs"><span class="hs-identifier hs-var">G.dfs</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; Graph
forall a. Graph a -&gt; Graph
</span><a href="Distribution.Compat.Graph.html#graphForward"><span class="hs-identifier hs-var hs-var">graphForward</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650561"><span class="hs-identifier hs-var">g</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[Vertex]
</span><a href="#local-6989586621679650559"><span class="hs-identifier hs-var">vs</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-309"></span><span>
</span><span id="line-310"></span><span class="hs-comment">-- | Compute the reverse closure of a graph from some set</span><span>
</span><span id="line-311"></span><span class="hs-comment">-- of keys.  Returns @Nothing@ if one (or more) keys are not present in</span><span>
</span><span id="line-312"></span><span class="hs-comment">-- the graph.</span><span>
</span><span id="line-313"></span><span class="hs-comment">-- Requires amortized construction of graph.</span><span>
</span><span id="line-314"></span><span id="local-6989586621679650555"><span class="annot"><a href="Distribution.Compat.Graph.html#revClosure"><span class="hs-identifier hs-type">revClosure</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679650555"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679650555"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Maybe"><span class="hs-identifier hs-type">Maybe</span></a></span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679650555"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span></span><span>
</span><span id="line-315"></span><span id="revClosure"><span class="annot"><span class="annottext">revClosure :: forall a. Graph a -&gt; [Key a] -&gt; Maybe [a]
</span><a href="Distribution.Compat.Graph.html#revClosure"><span class="hs-identifier hs-var hs-var">revClosure</span></a></span></span><span> </span><span id="local-6989586621679650550"><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650550"><span class="hs-identifier hs-var">g</span></a></span></span><span> </span><span id="local-6989586621679650549"><span class="annot"><span class="annottext">[Key a]
</span><a href="#local-6989586621679650549"><span class="hs-identifier hs-var">ks</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-keyword">do</span><span>
</span><span id="line-316"></span><span>    </span><span id="local-6989586621679650548"><span class="annot"><span class="annottext">[Vertex]
</span><a href="#local-6989586621679650548"><span class="hs-identifier hs-var">vs</span></a></span></span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">(Key a -&gt; Maybe Vertex) -&gt; [Key a] -&gt; Maybe [Vertex]
forall (t :: * -&gt; *) (f :: * -&gt; *) a b.
(Traversable t, Applicative f) =&gt;
(a -&gt; f b) -&gt; t a -&gt; f (t b)
</span><a href="../../base/src/Data.Traversable.html#traverse"><span class="hs-identifier hs-var">traverse</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; Key a -&gt; Maybe Vertex
forall a. Graph a -&gt; Key a -&gt; Maybe Vertex
</span><a href="Distribution.Compat.Graph.html#graphKeyToVertex"><span class="hs-identifier hs-var hs-var">graphKeyToVertex</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650550"><span class="hs-identifier hs-var">g</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[Key a]
</span><a href="#local-6989586621679650549"><span class="hs-identifier hs-var">ks</span></a></span><span>
</span><span id="line-317"></span><span>    </span><span class="annot"><span class="annottext">[a] -&gt; Maybe [a]
forall (m :: * -&gt; *) a. Monad m =&gt; a -&gt; m a
</span><a href="../../base/src/GHC.Base.html#return"><span class="hs-identifier hs-var">return</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; [Tree Vertex] -&gt; [a]
forall a. Graph a -&gt; [Tree Vertex] -&gt; [a]
</span><a href="Distribution.Compat.Graph.html#decodeVertexForest"><span class="hs-identifier hs-var">decodeVertexForest</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650550"><span class="hs-identifier hs-var">g</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph -&gt; [Vertex] -&gt; [Tree Vertex]
</span><a href="../../containers/src/Data.Graph.html#dfs"><span class="hs-identifier hs-var">G.dfs</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; Graph
forall a. Graph a -&gt; Graph
</span><a href="Distribution.Compat.Graph.html#graphAdjoint"><span class="hs-identifier hs-var hs-var">graphAdjoint</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650550"><span class="hs-identifier hs-var">g</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">[Vertex]
</span><a href="#local-6989586621679650548"><span class="hs-identifier hs-var">vs</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-318"></span><span>
</span><span id="line-319"></span><span id="local-6989586621679651059"><span class="annot"><a href="Distribution.Compat.Graph.html#flattenForest"><span class="hs-identifier hs-type">flattenForest</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="../../containers/src/Data.Tree.html#Forest"><span class="hs-identifier hs-type">Tree.Forest</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651059"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679651059"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span></span><span>
</span><span id="line-320"></span><span id="flattenForest"><span class="annot"><span class="annottext">flattenForest :: forall a. Forest a -&gt; [a]
</span><a href="Distribution.Compat.Graph.html#flattenForest"><span class="hs-identifier hs-var hs-var">flattenForest</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(Tree a -&gt; [a]) -&gt; [Tree a] -&gt; [a]
forall (t :: * -&gt; *) a b. Foldable t =&gt; (a -&gt; [b]) -&gt; t a -&gt; [b]
</span><a href="../../base/src/Data.Foldable.html#concatMap"><span class="hs-identifier hs-var">concatMap</span></a></span><span> </span><span class="annot"><span class="annottext">Tree a -&gt; [a]
forall a. Tree a -&gt; [a]
</span><a href="../../containers/src/Data.Tree.html#flatten"><span class="hs-identifier hs-var">Tree.flatten</span></a></span><span>
</span><span id="line-321"></span><span>
</span><span id="line-322"></span><span id="local-6989586621679651061"><span class="annot"><a href="Distribution.Compat.Graph.html#decodeVertexForest"><span class="hs-identifier hs-type">decodeVertexForest</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651061"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../containers/src/Data.Tree.html#Forest"><span class="hs-identifier hs-type">Tree.Forest</span></a></span><span> </span><span class="annot"><a href="../../containers/src/Data.Graph.html#Vertex"><span class="hs-identifier hs-type">G.Vertex</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679651061"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span></span><span>
</span><span id="line-323"></span><span id="decodeVertexForest"><span class="annot"><span class="annottext">decodeVertexForest :: forall a. Graph a -&gt; [Tree Vertex] -&gt; [a]
</span><a href="Distribution.Compat.Graph.html#decodeVertexForest"><span class="hs-identifier hs-var hs-var">decodeVertexForest</span></a></span></span><span> </span><span id="local-6989586621679650543"><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650543"><span class="hs-identifier hs-var">g</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(Vertex -&gt; a) -&gt; [Vertex] -&gt; [a]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; Vertex -&gt; a
forall a. Graph a -&gt; Vertex -&gt; a
</span><a href="Distribution.Compat.Graph.html#graphVertexToNode"><span class="hs-identifier hs-var hs-var">graphVertexToNode</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650543"><span class="hs-identifier hs-var">g</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">([Vertex] -&gt; [a])
-&gt; ([Tree Vertex] -&gt; [Vertex]) -&gt; [Tree Vertex] -&gt; [a]
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">[Tree Vertex] -&gt; [Vertex]
forall a. Forest a -&gt; [a]
</span><a href="Distribution.Compat.Graph.html#flattenForest"><span class="hs-identifier hs-var">flattenForest</span></a></span><span>
</span><span id="line-324"></span><span>
</span><span id="line-325"></span><span class="hs-comment">-- | Topologically sort the nodes of a graph.</span><span>
</span><span id="line-326"></span><span class="hs-comment">-- Requires amortized construction of graph.</span><span>
</span><span id="line-327"></span><span id="local-6989586621679650542"><span class="annot"><a href="Distribution.Compat.Graph.html#topSort"><span class="hs-identifier hs-type">topSort</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679650542"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679650542"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span></span><span>
</span><span id="line-328"></span><span id="topSort"><span class="annot"><span class="annottext">topSort :: forall a. Graph a -&gt; [a]
</span><a href="Distribution.Compat.Graph.html#topSort"><span class="hs-identifier hs-var hs-var">topSort</span></a></span></span><span> </span><span id="local-6989586621679650541"><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650541"><span class="hs-identifier hs-var">g</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(Vertex -&gt; a) -&gt; [Vertex] -&gt; [a]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; Vertex -&gt; a
forall a. Graph a -&gt; Vertex -&gt; a
</span><a href="Distribution.Compat.Graph.html#graphVertexToNode"><span class="hs-identifier hs-var hs-var">graphVertexToNode</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650541"><span class="hs-identifier hs-var">g</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">([Vertex] -&gt; [a]) -&gt; [Vertex] -&gt; [a]
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span> </span><span class="annot"><span class="annottext">Graph -&gt; [Vertex]
</span><a href="../../containers/src/Data.Graph.html#topSort"><span class="hs-identifier hs-var">G.topSort</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; Graph
forall a. Graph a -&gt; Graph
</span><a href="Distribution.Compat.Graph.html#graphForward"><span class="hs-identifier hs-var hs-var">graphForward</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650541"><span class="hs-identifier hs-var">g</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-329"></span><span>
</span><span id="line-330"></span><span class="hs-comment">-- | Reverse topologically sort the nodes of a graph.</span><span>
</span><span id="line-331"></span><span class="hs-comment">-- Requires amortized construction of graph.</span><span>
</span><span id="line-332"></span><span id="local-6989586621679650539"><span class="annot"><a href="Distribution.Compat.Graph.html#revTopSort"><span class="hs-identifier hs-type">revTopSort</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679650539"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679650539"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span></span><span>
</span><span id="line-333"></span><span id="revTopSort"><span class="annot"><span class="annottext">revTopSort :: forall a. Graph a -&gt; [a]
</span><a href="Distribution.Compat.Graph.html#revTopSort"><span class="hs-identifier hs-var hs-var">revTopSort</span></a></span></span><span> </span><span id="local-6989586621679650538"><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650538"><span class="hs-identifier hs-var">g</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(Vertex -&gt; a) -&gt; [Vertex] -&gt; [a]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; Vertex -&gt; a
forall a. Graph a -&gt; Vertex -&gt; a
</span><a href="Distribution.Compat.Graph.html#graphVertexToNode"><span class="hs-identifier hs-var hs-var">graphVertexToNode</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650538"><span class="hs-identifier hs-var">g</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">([Vertex] -&gt; [a]) -&gt; [Vertex] -&gt; [a]
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span> </span><span class="annot"><span class="annottext">Graph -&gt; [Vertex]
</span><a href="../../containers/src/Data.Graph.html#topSort"><span class="hs-identifier hs-var">G.topSort</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; Graph
forall a. Graph a -&gt; Graph
</span><a href="Distribution.Compat.Graph.html#graphAdjoint"><span class="hs-identifier hs-var hs-var">graphAdjoint</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650538"><span class="hs-identifier hs-var">g</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-334"></span><span>
</span><span id="line-335"></span><span class="hs-comment">-- Conversions</span><span>
</span><span id="line-336"></span><span>
</span><span id="line-337"></span><span class="hs-comment">-- | /O(1)/. Convert a map from keys to nodes into a graph.</span><span>
</span><span id="line-338"></span><span class="hs-comment">-- The map must satisfy the invariant that</span><span>
</span><span id="line-339"></span><span class="hs-comment">-- @'fromMap' m == 'fromList' ('Data.Map.elems' m)@;</span><span>
</span><span id="line-340"></span><span class="hs-comment">-- if you can't fulfill this invariant use @'fromList' ('Data.Map.elems' m)@</span><span>
</span><span id="line-341"></span><span class="hs-comment">-- instead.  The values of the map are assumed to already</span><span>
</span><span id="line-342"></span><span class="hs-comment">-- be in WHNF.</span><span>
</span><span id="line-343"></span><span id="local-6989586621679651106"><span class="annot"><a href="Distribution.Compat.Graph.html#fromMap"><span class="hs-identifier hs-type">fromMap</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#IsNode"><span class="hs-identifier hs-type">IsNode</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651106"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="annot"><a href="../../containers/src/Data.Map.Internal.html#Map"><span class="hs-identifier hs-type">Map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651106"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><a href="#local-6989586621679651106"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651106"><span class="hs-identifier hs-type">a</span></a></span></span><span>
</span><span id="line-344"></span><span id="fromMap"><span class="annot"><span class="annottext">fromMap :: forall a. IsNode a =&gt; Map (Key a) a -&gt; Graph a
</span><a href="Distribution.Compat.Graph.html#fromMap"><span class="hs-identifier hs-var hs-var">fromMap</span></a></span></span><span> </span><span id="local-6989586621679650516"><span class="annot"><span class="annottext">Map (Key a) a
</span><a href="#local-6989586621679650516"><span class="hs-identifier hs-var">m</span></a></span></span><span>
</span><span id="line-345"></span><span>    </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Graph :: forall a.
Map (Key a) a
-&gt; Graph
-&gt; Graph
-&gt; (Vertex -&gt; a)
-&gt; (Key a -&gt; Maybe Vertex)
-&gt; [(a, [Key a])]
-&gt; Graph a
</span><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="hs-special">{</span><span> </span><span class="annot"><span class="annottext">graphMap :: Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#graphMap"><span class="hs-identifier hs-var">graphMap</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Map (Key a) a
</span><a href="#local-6989586621679650516"><span class="hs-identifier hs-var">m</span></a></span><span>
</span><span id="line-346"></span><span>            </span><span class="hs-comment">-- These are lazily computed!</span><span>
</span><span id="line-347"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">graphForward :: Graph
</span><a href="Distribution.Compat.Graph.html#graphForward"><span class="hs-identifier hs-var">graphForward</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Graph
</span><a href="#local-6989586621679650515"><span class="hs-identifier hs-var">g</span></a></span><span>
</span><span id="line-348"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">graphAdjoint :: Graph
</span><a href="Distribution.Compat.Graph.html#graphAdjoint"><span class="hs-identifier hs-var">graphAdjoint</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Graph -&gt; Graph
</span><a href="../../containers/src/Data.Graph.html#transposeG"><span class="hs-identifier hs-var">G.transposeG</span></a></span><span> </span><span class="annot"><span class="annottext">Graph
</span><a href="#local-6989586621679650515"><span class="hs-identifier hs-var">g</span></a></span><span>
</span><span id="line-349"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">graphVertexToNode :: Vertex -&gt; a
</span><a href="Distribution.Compat.Graph.html#graphVertexToNode"><span class="hs-identifier hs-var">graphVertexToNode</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Vertex -&gt; a
</span><a href="#local-6989586621679650513"><span class="hs-identifier hs-var">vertex_to_node</span></a></span><span>
</span><span id="line-350"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">graphKeyToVertex :: Key a -&gt; Maybe Vertex
</span><a href="Distribution.Compat.Graph.html#graphKeyToVertex"><span class="hs-identifier hs-var">graphKeyToVertex</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Key a -&gt; Maybe Vertex
</span><a href="#local-6989586621679650512"><span class="hs-identifier hs-var">key_to_vertex</span></a></span><span>
</span><span id="line-351"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">graphBroken :: [(a, [Key a])]
</span><a href="Distribution.Compat.Graph.html#graphBroken"><span class="hs-identifier hs-var">graphBroken</span></a></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[(a, [Key a])]
</span><a href="#local-6989586621679650511"><span class="hs-identifier hs-var">broke</span></a></span><span>
</span><span id="line-352"></span><span>            </span><span class="hs-special">}</span><span>
</span><span id="line-353"></span><span>  </span><span class="hs-keyword">where</span><span>
</span><span id="line-354"></span><span>    </span><span id="local-6989586621679650510"><span class="annot"><span class="annottext">try_key_to_vertex :: Key a -&gt; Either (Key a) Vertex
</span><a href="#local-6989586621679650510"><span class="hs-identifier hs-var hs-var">try_key_to_vertex</span></a></span></span><span> </span><span id="local-6989586621679650509"><span class="annot"><span class="annottext">Key a
</span><a href="#local-6989586621679650509"><span class="hs-identifier hs-var">k</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Either (Key a) Vertex
-&gt; (Vertex -&gt; Either (Key a) Vertex)
-&gt; Maybe Vertex
-&gt; Either (Key a) Vertex
forall b a. b -&gt; (a -&gt; b) -&gt; Maybe a -&gt; b
</span><a href="../../base/src/Data.Maybe.html#maybe"><span class="hs-identifier hs-var">maybe</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Key a -&gt; Either (Key a) Vertex
forall a b. a -&gt; Either a b
</span><a href="../../base/src/Data.Either.html#Left"><span class="hs-identifier hs-var">Left</span></a></span><span> </span><span class="annot"><span class="annottext">Key a
</span><a href="#local-6989586621679650509"><span class="hs-identifier hs-var">k</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><span class="annottext">Vertex -&gt; Either (Key a) Vertex
forall a b. b -&gt; Either a b
</span><a href="../../base/src/Data.Either.html#Right"><span class="hs-identifier hs-var">Right</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Key a -&gt; Maybe Vertex
</span><a href="#local-6989586621679650512"><span class="hs-identifier hs-var">key_to_vertex</span></a></span><span> </span><span class="annot"><span class="annottext">Key a
</span><a href="#local-6989586621679650509"><span class="hs-identifier hs-var">k</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-355"></span><span>
</span><span id="line-356"></span><span>    </span><span class="hs-special">(</span><span id="local-6989586621679650507"><span class="annot"><span class="annottext">[[Key a]]
</span><a href="#local-6989586621679650507"><span class="hs-identifier hs-var">brokenEdges</span></a></span></span><span class="hs-special">,</span><span> </span><span id="local-6989586621679650506"><span class="annot"><span class="annottext">[[Vertex]]
</span><a href="#local-6989586621679650506"><span class="hs-identifier hs-var">edges</span></a></span></span><span class="hs-special">)</span><span>
</span><span id="line-357"></span><span>        </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[([Key a], [Vertex])] -&gt; ([[Key a]], [[Vertex]])
forall a b. [(a, b)] -&gt; ([a], [b])
</span><a href="../../base/src/GHC.List.html#unzip"><span class="hs-identifier hs-var">unzip</span></a></span><span>
</span><span id="line-358"></span><span>        </span><span class="annot"><span class="annottext">([([Key a], [Vertex])] -&gt; ([[Key a]], [[Vertex]]))
-&gt; [([Key a], [Vertex])] -&gt; ([[Key a]], [[Vertex]])
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span> </span><span class="hs-special">[</span><span> </span><span class="annot"><span class="annottext">[Either (Key a) Vertex] -&gt; ([Key a], [Vertex])
forall a b. [Either a b] -&gt; ([a], [b])
</span><a href="../../base/src/Data.Either.html#partitionEithers"><span class="hs-identifier hs-var">partitionEithers</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(Key a -&gt; Either (Key a) Vertex)
-&gt; [Key a] -&gt; [Either (Key a) Vertex]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="annot"><span class="annottext">Key a -&gt; Either (Key a) Vertex
</span><a href="#local-6989586621679650510"><span class="hs-identifier hs-var">try_key_to_vertex</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a -&gt; [Key a]
forall a. IsNode a =&gt; a -&gt; [Key a]
</span><a href="Distribution.Compat.Graph.html#nodeNeighbors"><span class="hs-identifier hs-var">nodeNeighbors</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679650503"><span class="hs-identifier hs-var">n</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-359"></span><span>          </span><span class="hs-glyph">|</span><span> </span><span id="local-6989586621679650503"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679650503"><span class="hs-identifier hs-var">n</span></a></span></span><span> </span><span class="hs-glyph">&lt;-</span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621679650502"><span class="hs-identifier hs-var">ns</span></a></span><span> </span><span class="hs-special">]</span><span>
</span><span id="line-360"></span><span>    </span><span id="local-6989586621679650511"><span class="annot"><span class="annottext">broke :: [(a, [Key a])]
</span><a href="#local-6989586621679650511"><span class="hs-identifier hs-var hs-var">broke</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">((a, [Key a]) -&gt; Bool) -&gt; [(a, [Key a])] -&gt; [(a, [Key a])]
forall a. (a -&gt; Bool) -&gt; [a] -&gt; [a]
</span><a href="../../base/src/GHC.List.html#filter"><span class="hs-identifier hs-var">filter</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Bool -&gt; Bool
</span><span class="hs-identifier hs-var">not</span></span><span> </span><span class="annot"><span class="annottext">(Bool -&gt; Bool) -&gt; ((a, [Key a]) -&gt; Bool) -&gt; (a, [Key a]) -&gt; Bool
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">[Key a] -&gt; Bool
forall (t :: * -&gt; *) a. Foldable t =&gt; t a -&gt; Bool
</span><a href="../../base/src/Data.Foldable.html#null"><span class="hs-identifier hs-var">Prelude.null</span></a></span><span> </span><span class="annot"><span class="annottext">([Key a] -&gt; Bool)
-&gt; ((a, [Key a]) -&gt; [Key a]) -&gt; (a, [Key a]) -&gt; Bool
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">(a, [Key a]) -&gt; [Key a]
forall a b. (a, b) -&gt; b
</span><a href="../../base/src/Data.Tuple.html#snd"><span class="hs-identifier hs-var">snd</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">[a] -&gt; [[Key a]] -&gt; [(a, [Key a])]
forall a b. [a] -&gt; [b] -&gt; [(a, b)]
</span><a href="../../base/src/GHC.List.html#zip"><span class="hs-identifier hs-var">zip</span></a></span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621679650502"><span class="hs-identifier hs-var">ns</span></a></span><span> </span><span class="annot"><span class="annottext">[[Key a]]
</span><a href="#local-6989586621679650507"><span class="hs-identifier hs-var">brokenEdges</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-361"></span><span>
</span><span id="line-362"></span><span>    </span><span id="local-6989586621679650515"><span class="annot"><span class="annottext">g :: Graph
</span><a href="#local-6989586621679650515"><span class="hs-identifier hs-var hs-var">g</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(Vertex, Vertex) -&gt; [[Vertex]] -&gt; Graph
forall i e. Ix i =&gt; (i, i) -&gt; [e] -&gt; Array i e
</span><a href="../../base/src/GHC.Arr.html#listArray"><span class="hs-identifier hs-var">Array.listArray</span></a></span><span> </span><span class="annot"><span class="annottext">(Vertex, Vertex)
</span><a href="#local-6989586621679650499"><span class="hs-identifier hs-var">bounds</span></a></span><span> </span><span class="annot"><span class="annottext">[[Vertex]]
</span><a href="#local-6989586621679650506"><span class="hs-identifier hs-var">edges</span></a></span><span>
</span><span id="line-363"></span><span>
</span><span id="line-364"></span><span>    </span><span id="local-6989586621679650502"><span class="annot"><span class="annottext">ns :: [a]
</span><a href="#local-6989586621679650502"><span class="hs-identifier hs-var hs-var">ns</span></a></span></span><span>              </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Map (Key a) a -&gt; [a]
forall k a. Map k a -&gt; [a]
</span><a href="../../containers/src/Data.Map.Internal.html#elems"><span class="hs-identifier hs-var">Map.elems</span></a></span><span> </span><span class="annot"><span class="annottext">Map (Key a) a
</span><a href="#local-6989586621679650516"><span class="hs-identifier hs-var">m</span></a></span><span> </span><span class="hs-comment">-- sorted ascending</span><span>
</span><span id="line-365"></span><span>    </span><span id="local-6989586621679650497"><span class="annot"><span class="annottext">vertices :: [(Key a, Vertex)]
</span><a href="#local-6989586621679650497"><span class="hs-identifier hs-var hs-var">vertices</span></a></span></span><span>        </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[Key a] -&gt; [Vertex] -&gt; [(Key a, Vertex)]
forall a b. [a] -&gt; [b] -&gt; [(a, b)]
</span><a href="../../base/src/GHC.List.html#zip"><span class="hs-identifier hs-var">zip</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">(a -&gt; Key a) -&gt; [a] -&gt; [Key a]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; Key a
forall a. IsNode a =&gt; a -&gt; Key a
</span><a href="Distribution.Compat.Graph.html#nodeKey"><span class="hs-identifier hs-var">nodeKey</span></a></span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621679650502"><span class="hs-identifier hs-var">ns</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-special">[</span><span class="annot"><span class="annottext">Vertex
</span><span class="hs-number">0</span></span><span class="hs-glyph">..</span><span class="hs-special">]</span><span>
</span><span id="line-366"></span><span>    </span><span id="local-6989586621679650496"><span class="annot"><span class="annottext">vertex_map :: Map (Key a) Vertex
</span><a href="#local-6989586621679650496"><span class="hs-identifier hs-var hs-var">vertex_map</span></a></span></span><span>      </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">[(Key a, Vertex)] -&gt; Map (Key a) Vertex
forall k a. Eq k =&gt; [(k, a)] -&gt; Map k a
</span><a href="../../containers/src/Data.Map.Strict.Internal.html#fromAscList"><span class="hs-identifier hs-var">Map.fromAscList</span></a></span><span> </span><span class="annot"><span class="annottext">[(Key a, Vertex)]
</span><a href="#local-6989586621679650497"><span class="hs-identifier hs-var">vertices</span></a></span><span>
</span><span id="line-367"></span><span>    </span><span id="local-6989586621679650512"><span class="annot"><span class="annottext">key_to_vertex :: Key a -&gt; Maybe Vertex
</span><a href="#local-6989586621679650512"><span class="hs-identifier hs-var hs-var">key_to_vertex</span></a></span></span><span> </span><span id="local-6989586621679650494"><span class="annot"><span class="annottext">Key a
</span><a href="#local-6989586621679650494"><span class="hs-identifier hs-var">k</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Key a -&gt; Map (Key a) Vertex -&gt; Maybe Vertex
forall k a. Ord k =&gt; k -&gt; Map k a -&gt; Maybe a
</span><a href="../../containers/src/Data.Map.Internal.html#lookup"><span class="hs-identifier hs-var">Map.lookup</span></a></span><span> </span><span class="annot"><span class="annottext">Key a
</span><a href="#local-6989586621679650494"><span class="hs-identifier hs-var">k</span></a></span><span> </span><span class="annot"><span class="annottext">Map (Key a) Vertex
</span><a href="#local-6989586621679650496"><span class="hs-identifier hs-var">vertex_map</span></a></span><span>
</span><span id="line-368"></span><span>
</span><span id="line-369"></span><span>    </span><span id="local-6989586621679650513"><span class="annot"><span class="annottext">vertex_to_node :: Vertex -&gt; a
</span><a href="#local-6989586621679650513"><span class="hs-identifier hs-var hs-var">vertex_to_node</span></a></span></span><span> </span><span id="local-6989586621679650493"><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621679650493"><span class="hs-identifier hs-var">vertex</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Array Vertex a
</span><a href="#local-6989586621679650492"><span class="hs-identifier hs-var">nodeTable</span></a></span><span> </span><span class="annot"><span class="annottext">Array Vertex a -&gt; Vertex -&gt; a
forall i e. Ix i =&gt; Array i e -&gt; i -&gt; e
</span><a href="../../base/src/GHC.Arr.html#%21"><span class="hs-operator hs-var">!</span></a></span><span> </span><span class="annot"><span class="annottext">Vertex
</span><a href="#local-6989586621679650493"><span class="hs-identifier hs-var">vertex</span></a></span><span>
</span><span id="line-370"></span><span>
</span><span id="line-371"></span><span>    </span><span id="local-6989586621679650492"><span class="annot"><span class="annottext">nodeTable :: Array Vertex a
</span><a href="#local-6989586621679650492"><span class="hs-identifier hs-var hs-var">nodeTable</span></a></span></span><span>   </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">(Vertex, Vertex) -&gt; [a] -&gt; Array Vertex a
forall i e. Ix i =&gt; (i, i) -&gt; [e] -&gt; Array i e
</span><a href="../../base/src/GHC.Arr.html#listArray"><span class="hs-identifier hs-var">Array.listArray</span></a></span><span> </span><span class="annot"><span class="annottext">(Vertex, Vertex)
</span><a href="#local-6989586621679650499"><span class="hs-identifier hs-var">bounds</span></a></span><span> </span><span class="annot"><span class="annottext">[a]
</span><a href="#local-6989586621679650502"><span class="hs-identifier hs-var">ns</span></a></span><span>
</span><span id="line-372"></span><span>    </span><span id="local-6989586621679650499"><span class="annot"><span class="annottext">bounds :: (Vertex, Vertex)
</span><a href="#local-6989586621679650499"><span class="hs-identifier hs-var hs-var">bounds</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Vertex
</span><span class="hs-number">0</span></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">Map (Key a) a -&gt; Vertex
forall k a. Map k a -&gt; Vertex
</span><a href="../../containers/src/Data.Map.Internal.html#size"><span class="hs-identifier hs-var">Map.size</span></a></span><span> </span><span class="annot"><span class="annottext">Map (Key a) a
</span><a href="#local-6989586621679650516"><span class="hs-identifier hs-var">m</span></a></span><span> </span><span class="annot"><span class="annottext">Vertex -&gt; Vertex -&gt; Vertex
forall a. Num a =&gt; a -&gt; a -&gt; a
</span><a href="../../base/src/GHC.Num.html#-"><span class="hs-glyph hs-var">-</span></a></span><span> </span><span class="annot"><span class="annottext">Vertex
</span><span class="hs-number">1</span></span><span class="hs-special">)</span><span>
</span><span id="line-373"></span><span>
</span><span id="line-374"></span><span class="hs-comment">-- | /O(V log V)/. Convert a list of nodes (with distinct keys) into a graph.</span><span>
</span><span id="line-375"></span><span id="local-6989586621679651213"><span class="annot"><a href="Distribution.Compat.Graph.html#fromDistinctList"><span class="hs-identifier hs-type">fromDistinctList</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Compat.Graph.html#IsNode"><span class="hs-identifier hs-type">IsNode</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651213"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../base/src/GHC.Show.html#Show"><span class="hs-identifier hs-type">Show</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651213"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span> </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679651213"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651213"><span class="hs-identifier hs-type">a</span></a></span></span><span>
</span><span id="line-376"></span><span id="fromDistinctList"><span class="annot"><span class="annottext">fromDistinctList :: forall a. (IsNode a, Show (Key a)) =&gt; [a] -&gt; Graph a
</span><a href="Distribution.Compat.Graph.html#fromDistinctList"><span class="hs-identifier hs-var hs-var">fromDistinctList</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Map (Key a) a -&gt; Graph a
forall a. IsNode a =&gt; Map (Key a) a -&gt; Graph a
</span><a href="Distribution.Compat.Graph.html#fromMap"><span class="hs-identifier hs-var">fromMap</span></a></span><span>
</span><span id="line-377"></span><span>                 </span><span class="annot"><span class="annottext">(Map (Key a) a -&gt; Graph a)
-&gt; ([a] -&gt; Map (Key a) a) -&gt; [a] -&gt; Graph a
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">(a -&gt; a -&gt; a) -&gt; [(Key a, a)] -&gt; Map (Key a) a
forall k a. Ord k =&gt; (a -&gt; a -&gt; a) -&gt; [(k, a)] -&gt; Map k a
</span><a href="../../containers/src/Data.Map.Strict.Internal.html#fromListWith"><span class="hs-identifier hs-var">Map.fromListWith</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-glyph">\</span><span class="annot"><span class="annottext">a
</span><span class="hs-identifier">_</span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">a -&gt; a
forall {a} {a}. (Show (Key a), IsNode a) =&gt; a -&gt; a
</span><a href="#local-6989586621679650480"><span class="hs-identifier hs-var">duplicateError</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-378"></span><span>                 </span><span class="annot"><span class="annottext">([(Key a, a)] -&gt; Map (Key a) a)
-&gt; ([a] -&gt; [(Key a, a)]) -&gt; [a] -&gt; Map (Key a) a
forall b c a. (b -&gt; c) -&gt; (a -&gt; b) -&gt; a -&gt; c
</span><a href="../../base/src/GHC.Base.html#."><span class="hs-operator hs-var">.</span></a></span><span> </span><span class="annot"><span class="annottext">(a -&gt; (Key a, a)) -&gt; [a] -&gt; [(Key a, a)]
forall a b. (a -&gt; b) -&gt; [a] -&gt; [b]
</span><a href="../../base/src/GHC.Base.html#map"><span class="hs-identifier hs-var">map</span></a></span><span> </span><span class="hs-special">(</span><span class="hs-glyph">\</span><span id="local-6989586621679650479"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679650479"><span class="hs-identifier hs-var">n</span></a></span></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679650479"><span class="hs-identifier hs-var">n</span></a></span><span> </span><span class="annot"><span class="annottext">a -&gt; (Key a, a) -&gt; (Key a, a)
</span><span class="hs-operator hs-var">`seq`</span></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a -&gt; Key a
forall a. IsNode a =&gt; a -&gt; Key a
</span><a href="Distribution.Compat.Graph.html#nodeKey"><span class="hs-identifier hs-var">nodeKey</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679650479"><span class="hs-identifier hs-var">n</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679650479"><span class="hs-identifier hs-var">n</span></a></span><span class="hs-special">)</span><span class="hs-special">)</span><span>
</span><span id="line-379"></span><span>  </span><span class="hs-keyword">where</span><span>
</span><span id="line-380"></span><span>    </span><span id="local-6989586621679650480"><span class="annot"><span class="annottext">duplicateError :: a -&gt; a
</span><a href="#local-6989586621679650480"><span class="hs-identifier hs-var hs-var">duplicateError</span></a></span></span><span> </span><span id="local-6989586621679650469"><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679650469"><span class="hs-identifier hs-var">n</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">String -&gt; a
forall a. HasCallStack =&gt; String -&gt; a
</span><a href="../../base/src/GHC.Err.html#error"><span class="hs-identifier hs-var">error</span></a></span><span> </span><span class="annot"><span class="annottext">(String -&gt; a) -&gt; String -&gt; a
forall a b. (a -&gt; b) -&gt; a -&gt; b
</span><a href="../../base/src/GHC.Base.html#%24"><span class="hs-operator hs-var">$</span></a></span><span> </span><span class="annot"><span class="annottext">String
</span><span class="hs-string">&quot;Graph.fromDistinctList: duplicate key: &quot;</span></span><span>
</span><span id="line-381"></span><span>                            </span><span class="annot"><span class="annottext">String -&gt; ShowS
forall a. [a] -&gt; [a] -&gt; [a]
</span><a href="../../base/src/GHC.Base.html#%2B%2B"><span class="hs-operator hs-var">++</span></a></span><span> </span><span class="annot"><span class="annottext">Key a -&gt; String
forall a. Show a =&gt; a -&gt; String
</span><a href="../../base/src/GHC.Show.html#show"><span class="hs-identifier hs-var">show</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">a -&gt; Key a
forall a. IsNode a =&gt; a -&gt; Key a
</span><a href="Distribution.Compat.Graph.html#nodeKey"><span class="hs-identifier hs-var">nodeKey</span></a></span><span> </span><span class="annot"><span class="annottext">a
</span><a href="#local-6989586621679650469"><span class="hs-identifier hs-var">n</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-382"></span><span>
</span><span id="line-383"></span><span class="hs-comment">-- Map-like operations</span><span>
</span><span id="line-384"></span><span>
</span><span id="line-385"></span><span class="hs-comment">-- | /O(V)/. Convert a graph into a list of nodes.</span><span>
</span><span id="line-386"></span><span id="local-6989586621679651221"><span class="annot"><a href="Distribution.Compat.Graph.html#toList"><span class="hs-identifier hs-type">toList</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651221"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="#local-6989586621679651221"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span></span><span>
</span><span id="line-387"></span><span id="toList"><span class="annot"><span class="annottext">toList :: forall a. Graph a -&gt; [a]
</span><a href="Distribution.Compat.Graph.html#toList"><span class="hs-identifier hs-var hs-var">toList</span></a></span></span><span> </span><span id="local-6989586621679650467"><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650467"><span class="hs-identifier hs-var">g</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Map (Key a) a -&gt; [a]
forall k a. Map k a -&gt; [a]
</span><a href="../../containers/src/Data.Map.Internal.html#elems"><span class="hs-identifier hs-var">Map.elems</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#toMap"><span class="hs-identifier hs-var">toMap</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650467"><span class="hs-identifier hs-var">g</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-388"></span><span>
</span><span id="line-389"></span><span class="hs-comment">-- | /O(V)/. Convert a graph into a list of keys.</span><span>
</span><span id="line-390"></span><span id="local-6989586621679651014"><span class="annot"><a href="Distribution.Compat.Graph.html#keys"><span class="hs-identifier hs-type">keys</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651014"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">[</span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651014"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">]</span></span><span>
</span><span id="line-391"></span><span id="keys"><span class="annot"><span class="annottext">keys :: forall a. Graph a -&gt; [Key a]
</span><a href="Distribution.Compat.Graph.html#keys"><span class="hs-identifier hs-var hs-var">keys</span></a></span></span><span> </span><span id="local-6989586621679650466"><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650466"><span class="hs-identifier hs-var">g</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Map (Key a) a -&gt; [Key a]
forall k a. Map k a -&gt; [k]
</span><a href="../../containers/src/Data.Map.Internal.html#keys"><span class="hs-identifier hs-var">Map.keys</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#toMap"><span class="hs-identifier hs-var">toMap</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650466"><span class="hs-identifier hs-var">g</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-392"></span><span>
</span><span id="line-393"></span><span class="hs-comment">-- | /O(V)/. Convert a graph into a set of keys.</span><span>
</span><span id="line-394"></span><span id="local-6989586621679651010"><span class="annot"><a href="Distribution.Compat.Graph.html#keysSet"><span class="hs-identifier hs-type">keysSet</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651010"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../containers/src/Data.Set.Internal.html#Set"><span class="hs-identifier hs-type">Set.Set</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651010"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span></span><span>
</span><span id="line-395"></span><span id="keysSet"><span class="annot"><span class="annottext">keysSet :: forall a. Graph a -&gt; Set (Key a)
</span><a href="Distribution.Compat.Graph.html#keysSet"><span class="hs-identifier hs-var hs-var">keysSet</span></a></span></span><span> </span><span id="local-6989586621679650464"><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650464"><span class="hs-identifier hs-var">g</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Map (Key a) a -&gt; Set (Key a)
forall k a. Map k a -&gt; Set k
</span><a href="../../containers/src/Data.Map.Internal.html#keysSet"><span class="hs-identifier hs-var">Map.keysSet</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#toMap"><span class="hs-identifier hs-var">toMap</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650464"><span class="hs-identifier hs-var">g</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-396"></span><span>
</span><span id="line-397"></span><span class="hs-comment">-- | /O(1)/. Convert a graph into a map from keys to nodes.</span><span>
</span><span id="line-398"></span><span class="hs-comment">-- The resulting map @m@ is guaranteed to have the property that</span><span>
</span><span id="line-399"></span><span class="hs-comment">-- @'Prelude.all' (\(k,n) -&gt; k == 'nodeKey' n) ('Data.Map.toList' m)@.</span><span>
</span><span id="line-400"></span><span id="local-6989586621679650462"><span class="annot"><a href="Distribution.Compat.Graph.html#toMap"><span class="hs-identifier hs-type">toMap</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679650462"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../containers/src/Data.Map.Internal.html#Map"><span class="hs-identifier hs-type">Map</span></a></span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679650462"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span> </span><span class="annot"><a href="#local-6989586621679650462"><span class="hs-identifier hs-type">a</span></a></span></span><span>
</span><span id="line-401"></span><span id="toMap"><span class="annot"><span class="annottext">toMap :: forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#toMap"><span class="hs-identifier hs-var hs-var">toMap</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">Graph a -&gt; Map (Key a) a
forall a. Graph a -&gt; Map (Key a) a
</span><a href="Distribution.Compat.Graph.html#graphMap"><span class="hs-identifier hs-var hs-var">graphMap</span></a></span><span>
</span><span id="line-402"></span><span>
</span><span id="line-403"></span><span class="hs-comment">-- Graph-like operations</span><span>
</span><span id="line-404"></span><span>
</span><span id="line-405"></span><span class="hs-comment">-- | /O(1)/. Convert a graph into a 'Data.Graph.Graph'.</span><span>
</span><span id="line-406"></span><span class="hs-comment">-- Requires amortized construction of graph.</span><span>
</span><span id="line-407"></span><span id="local-6989586621679651004"><span class="annot"><a href="Distribution.Compat.Graph.html#toGraph"><span class="hs-identifier hs-type">toGraph</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Graph"><span class="hs-identifier hs-type">Graph</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651004"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="../../containers/src/Data.Graph.html#Graph"><span class="hs-identifier hs-type">G.Graph</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="../../containers/src/Data.Graph.html#Vertex"><span class="hs-identifier hs-type">G.Vertex</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679651004"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Distribution.Compat.Graph.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679651004"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="../../base/src/GHC.Maybe.html#Maybe"><span class="hs-identifier hs-type">Maybe</span></a></span><span> </span><span class="annot"><a href="../../containers/src/Data.Graph.html#Vertex"><span class="hs-identifier hs-type">G.Vertex</span></a></span><span class="hs-special">)</span></span><span>
</span><span id="line-408"></span><span id="toGraph"><span class="annot"><span class="annottext">toGraph :: forall a. Graph a -&gt; (Graph, Vertex -&gt; a, Key a -&gt; Maybe Vertex)
</span><a href="Distribution.Compat.Graph.html#toGraph"><span class="hs-identifier hs-var hs-var">toGraph</span></a></span></span><span> </span><span id="local-6989586621679650461"><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650461"><span class="hs-identifier hs-var">g</span></a></span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="hs-special">(</span><span class="annot"><span class="annottext">Graph a -&gt; Graph
forall a. Graph a -&gt; Graph
</span><a href="Distribution.Compat.Graph.html#graphForward"><span class="hs-identifier hs-var hs-var">graphForward</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650461"><span class="hs-identifier hs-var">g</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">Graph a -&gt; Vertex -&gt; a
forall a. Graph a -&gt; Vertex -&gt; a
</span><a href="Distribution.Compat.Graph.html#graphVertexToNode"><span class="hs-identifier hs-var hs-var">graphVertexToNode</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650461"><span class="hs-identifier hs-var">g</span></a></span><span class="hs-special">,</span><span> </span><span class="annot"><span class="annottext">Graph a -&gt; Key a -&gt; Maybe Vertex
forall a. Graph a -&gt; Key a -&gt; Maybe Vertex
</span><a href="Distribution.Compat.Graph.html#graphKeyToVertex"><span class="hs-identifier hs-var hs-var">graphKeyToVertex</span></a></span><span> </span><span class="annot"><span class="annottext">Graph a
</span><a href="#local-6989586621679650461"><span class="hs-identifier hs-var">g</span></a></span><span class="hs-special">)</span><span>
</span><span id="line-409"></span></pre></body></html>